质数计算器不适用于大数

Question

我正在尝试打印出一个数的所有质因数。我的代码如下：

public static boolean isPrime(long n){

    long i = n;

    while (i > 0){

        if (n % i == 0 && !(i == 1 || i == n)){

            return false;

        }
        i--;
    }

    return true;

}


public static void primeFactors(long n){

    long i = n;
    while (i > 0){

        if (isPrime(i)){
            System.out.println(i);
        }
        i--;
    }

}

此代码适用于较小的数字：5、5000，例如当我向该方法输入 600851475143 时，我的程序运行并且没有任何输出。为什么会这样？

Answer 1

当给定输入数字 600851475143 时，您的程序没有打印任何内容，因为您检查质数的方式很慢。只要有足够的耐心，您的程序就会打印一些东西——但这可能需要数小时、数天甚至数年。您需要为此计算提出更好的算法。

Answer 2

你的素性测试函数太糟糕了。

快速取胜：向前数而不是向后数。目前，您至少会数到一半的数字，直到找到一个因数！这可能是您观察到的延迟的原因。
更好一点：计算奇数直到平方根。
也许更好：计算素数直到平方根。根据要求使用筛子预先计算。

Answer 3

简短回答：程序实际上并没有终止。您使用的方法是检查素数的最低效方法之一。查看 Sieve of Eratosthenes 以获得易于理解且相当高效的算法。

Answer 4

不需要检查n个数来检查n是不是素数，从0开始就够了n/2:

public static boolean isPrime(long n){

        long i = 2;

        while (i < n/2){

            if (n % i == 0 ){

                return false;

            }
            i++;
        }

        return true;

    }

这将使性能翻倍

Answer 5

虽然数字没有超出长原始值范围 (9,223,372,036,854,775,807)，但您应该使用 BigInteger，因为 BigInteger 具有用于此目的的功能，而且我认为它比包括您在内的其他实现更有效。

new BigInteger(yourNumer).isProbablePrime(100) // returns true or false

此外，素数测试是通过使用许多数学方法和算法完成的，有一些方法对于 < 64 位的数字运行速度更快，还有一些方法可以更好地测试更大的数字。还有其他一些方法here

Answer 6

将您的方法更改为以下内容：

public static boolean isPrime(long num) {
    for (int i = 2; i < Math.sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

应该够高效了。

Answer 7

其他答案都集中在您的功能 isPrime 上，该功能效率低下。我将转而关注您的函数 primeFactors，这是不正确的。实际上，您可以看到它以相反的顺序打印了直到 n 的素数，而不是 n 的素因数。相反，做

public static void primeFactors(long n) {
  // Handle factors of 2
  while (n%2==0) {
    System.out.println(2);
    n /= 2;
  }

  // Handle all odd prime factors except the largest
  for (long p = 3; p*p <= n; p += 2) {
    while (n%p == 0) {
      System.out.println(p);
      n /= p;
    }
  }

  // Handle the largest prime factor
  if (n > 1) {
    System.out.println(2);
  }
}

您可能会注意到从未使用过 isPrime！其实不需要：只要你找到它们就把它们去掉，你打印的所有数字都是质数。

这里有很多可能的改进，但这种方法目前已经足够快了。一种简单的方法是计算 Math.sqrt(n) 的上限并将 p 与其进行比较，而不是每次都将 p 乘以自身。您可能还想检查 0 和负数，可能还有 1，具体取决于您要如何处理这些数字。

质数计算器不适用于大数

Prime Number Calculator Not Working With Large Numbers

java

prime-factoring