素数计算器不使用大数字

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

你的素性测试功能很糟糕.

1. 快速获胜:向前计数而不是倒退.目前,您将计算至少一半的数量,直到找到一个因素!这可能是你观察到的延迟的原因.

2. 更好一点:计算奇数到平方根.

3. 也许更好的是:将素数计算到平方根.根据要求预先计算使用筛子的那些.