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

Question

从 user.Then 打印第 n 个至少具有 4 个不同质因数的数字中获取数字 n。例如（210 个质因数（2,3,5,7）） 210 是第一个具有 4 个不同质因数的数字，下一个数字是 330(2,3,5,11)。 Input:2 output:330 和 Input:3 output: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;
        }
    }
}

解释：

循环从210迭代到第n个有四个或更多的数字不同的主要因素。
对于每个满足标准的数字，方法 returns true else false。
接下来检查列表的大小是否等于用户输入的数字 (n)。如果它等于第n-1 获取索引并退出循环。

Answer 2

上述方法的一个问题是它除以所有奇数直到候选人的平方根。最好除以以前累积的素数。这很容易完成，如下所示：

      List<Integer> primes = new ArrayList<>(List.of(2));
      outer:
      for (int i = 3; i < n; i++) {
         int end = (int)Math.sqrt(i);
         for (int k = 0, p = primes.get(0); p <= end; p =
               primes.get(k++)) {
            if (i % p == 0) {
               continue outer;
            }
         }
         primes.add(i);
      }

并将平方根计算移出循环。它在每个周期都被评估。

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

Find the number that has 4 distinct prime factors

java

prime-factoring