java - 找出具有 4 个不同质因数的数字

Question

从用户处获取数字 n。然后打印第 n 个具有至少 4 个不同质因数的数字。例如(210素因数(2,3,5,7)) 210是第一个具有4个不同素因数的数字，下一个数字是330(2,3,5,11)。 输入:2 输出:330 和输入:3 输出:390。我不知道该怎么做？我试图找到一个数字的质因数。

 for (int i = 2; i <= number; i++) {
     while (number % i == 0) {
        System.out.print(i + " ");
        number = number / i;
     }
 }
 if (number < 1) 
     System.out.println(number);

但我想打印第 n 个具有 4 个不同质因数的数字。

Answer 1

您可以使用以下代码:

public static boolean findPrimeFactors(int n) {
    Set<Integer> primeFactorSet = new HashSet<>();
    while (n % 2 == 0) {
        // here number is even so adding 2
        primeFactorSet.add(2);
        n /= 2;
    }

    // number would be odd in this loop
    for (int i = 3; i <= Math.sqrt(n); i += 2) {
        while (n % i == 0) {
            primeFactorSet.add(i);
            n /= i;
        }
    }

    if (n > 2) {
        primeFactorSet.add(n);
    }

    // true if the unique prime-factors are greater than or equal to 4
    return primeFactorSet.size() >= 4 ? true : false;
}

现在使用以下方式调用它:

public static void main(String[] args) {
    List<Integer> primeFactorList = new ArrayList<Integer>();
    // accept this from user
    int n = 2;

    for (int i = 210;; i++) {
        // find prime factors for each number
        if (findPrimeFactors(i)) {
            primeFactorList.add(i);
        }
        if (primeFactorList.size() == n) {
            System.out.println(primeFactorList.get(n - 1));
            break;
        }
    }
}

说明:

1. 循环从 210 迭代直到第 n 个具有 4 或更多的数字 不同的质因数。
2. 对于每个满足条件的数字，该方法返回 true，否则返回 false。
3. 接下来检查列表的大小是否等于 用户输入的数字 (n)。如果它等于第 n-1 个 获取索引并退出循环。