java - 无法在一个范围内找到 DISTINCT 素因子的 NUMBER

Question

顽皮数是指其不同素数的个数等于其十进制表示中的位数的数。 数字 1 被认为是一个顽皮的数字。下面是查找顽皮号码的代码。问题出在方法素数上，死循环。

import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeSet;
import java.util.Iterator; 

public class NaughtyNumber {
    ArrayList < Integer > aldecrep = new ArrayList < > (); // use for decimal representation
    TreeSet < Integer > tsprimefact = new TreeSet < > (); // use for store of prime factors       
    ArrayList < Integer > alsize1 = new ArrayList < > (); // use for storing  number of prime factors
    public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int query, ul, dl;
            System.out.println("Enter the nuber of queries");
            query = in .nextInt();
            System.out.println("Enter upperlimit and down limit");
            while (query != 0) {
                dl = in .nextInt();
                ul = in .nextInt();
                NaughtyNumber n1 = new NaughtyNumber();
                //NaughtyNumber n2=new NaughtyNumber();
                //NaughtyNumber n3=new NaughtyNumber();
                n1.decal(dl, ul);
                n1.primefactor(dl, ul);
                n1.compare(dl);
                query--;
            }
        }
        //count number of digits        
    void decal(int dl, int ul) {
            for (int i = dl; i <= ul; i++) {
                int length = (int)(Math.log10(i) + 1); //calculation of length of a     number
                aldecrep.add(length);
            }
        }
        //count number of digits ends
        //prime factorization starts
    void primefactor(int dl, int ul) {
            for (int i = dl; i <= ul; i++) {
                for (int j = 2; j <= i; j++) {
                    if (i % j == 0) {
                        i = i / j;
                        tsprimefact.add(j); // add distinct prime factors
                        j--;
                    }

                    alsize1.add(tsprimefact.size()); //add treesize to set size1
                    tsprimefact.clear(); //empty ts

                }
            }
            Iterator < Integer > itr1 = alsize1.iterator();
            while (itr1.hasNext()) {
                Integer n1 = itr1.next();
                System.out.println(n1);
            }
        }
        //prime factorization ends      
        // compare to find naughty number
    void compare(int dl) {
        Iterator < Integer > itr = aldecrep.iterator();
        Iterator < Integer > itr1 = alsize1.iterator();
        int count = 0;
        if (dl == 1) {
            count = count + 1;
        }
        while (itr.hasNext() && itr1.hasNext()) {
            Integer n1 = itr.next();
            Integer n2 = itr1.next();
            if (n1 == n2) {
                count++;
            }
        }
        System.out.println(count);
    }
}

Answer 1

使用这样的因式分解:

public static Set<Integer> primeFactors(int numbers) {
    int n = numbers;
    Set<Integer> factors = new HashSet<Integer>();
    for (int i = 2; i <= n / i; i++) {
      while (n % i == 0) {
        factors.add(i);
        n /= i;
      }
    }
    if (n > 1) {
      factors.add(n);
    }
    return factors;
  }

我修改了http://www.vogella.com/tutorials/JavaAlgorithmsPrimeFactorization/article.html的源码

Set 以类似DISTINCT 的方式减少元素。