c++ - 如何为任何值编码 Euler #3？

Question

/*
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
*/

#include <iostream>
#include <string>
#include <cmath>

using namespace std;


int main()
{
    unsigned long num = 600851475143;
    unsigned long i;
    long double root = sqrt(num);
    long double tempRoot = 0;
    unsigned long factor = 0;
    unsigned long largest = 0;

    for (i=2; i<root; i++)
    {
        if (num%i == 0)
        {   
            num = num/i;
            factor = i;
            cout << factor << endl;

            if (factor > largest)
                {
                    largest = factor;
                }
        }
    }

    cout << largest << endl;    

return 0;
}

这个解决方案之所以可行，是因为巧合的是 600851475143 的因子都是质数。但是在调试代码时，我为变量 num (=600851475143) 输入了各种值。例如，当我输入 135 时，它显示了所有因子，包括非素数。如何为因子添加质数检查器？我尝试在嵌套 if 中使用我在此处使用的相同方法，但失败得很惨。任何帮助将不胜感激。

此外，请指出我是否在某些变量的情况下使用了不必要的大变量类型。

谢谢。

Answer 1

您不必进行素数检查。当您进行因式分解时，请确保继续划分候选人，直到它不再划分数字为止。这在代码中很容易做到:只需将 if (num%i == 0) 更改为 while (num%i == 0)。