项目欧拉问题3帮助

Question

我正在尝试通过Project Euler工作,我在问题03上遇到障碍.我有一个适用于较小数字的算法,但问题3使用非常非常大的数字.

问题03: 13195的主要因素是5,7,13和29. 600851475143中最大的素数因子是什么？

这是我在C#中的解决方案,它一直在运行,我认为接近一个小时.我不是在寻找答案,因为我确实想自己解决这个问题.主要是寻求一些帮助.

    static void Main(string[] args) {
        const long n = 600851475143;
        //const long n = 13195;
        long count, half, largestPrime = 0;
        bool IsAPrime;

        half = n / 2;

        for (long i = half; i > 1 && largestPrime == 0; i--) {
             if (n % i == 0) { // these are factors of n
                count = 1;
                IsAPrime = true;
                while (++count < i && IsAPrime) {
                    if (i % count == 0) { // does a factor of n have a factor? (not prime)
                        IsAPrime = false;
                    }
                }
                if (IsAPrime) {
                    largestPrime = i;
                }
            }
        }

        Console.WriteLine("The largest prime factor is " + largestPrime.ToString() + ".");
        Console.ReadLine();
    }

Answer 1

首先,不是在n/2开始搜索,而是从n的平方根开始.你会得到一半的因素,另一半是他们的补充.

例如:

n = 27
start at floor(sqrt(27)) = 5
is 5 a factor? no
is 4 a factor? no
is 3 a factor? yes. 27 / 3 = 9. 9 is also a factor.
is 2 a factor? no.
factors are 3 and 9.

Answer 2

虽然这个问题要求最大的素因子,但这并不一定意味着你必须首先找到那个......

Answer 3

实际上,对于这种情况,您不需要检查素数,只需删除您找到的因子.从n == 2开始向上扫描.当邪恶的大数字%n == 0时,将邪恶的大数字除以n并继续使用较小的邪恶数字.当n> = sqrt(big-evil-number)时停止.

在任何现代机器上都不应该花费超过几秒钟.

Answer 4

long n = 600851475143L; //not even, so 2 wont be a factor
int factor = 3; 
while( n > 1)
{
    if(n % factor == 0)
    {
        n/=factor;
    }else
        factor += 2; //skip even numbrs
}
        print factor;

这应该足够快......注意,没有必要检查素数......

Answer 5

您需要减少正在进行的检查量...想想您需要测试的数字.

为了更好的方法阅读Erathosthenes的筛子 ......它应该让你指向正确的方向.