c - 破解项目欧拉问题3，我的解决方案正确吗？

Question

欧拉项目问题3如下：
13195的主因子有5、7、13和29。
600851475143中最大的素因数是什么？
我已经做了这个解决方案，有意义，看起来不错，适用于小数字，但当我们谈到这个问题时，大数字就是程序永远运行的时候我的问题是，这从根本上说是正确的吗？如果是，我如何优化代码？据我所知，有问题的函数是_prime（）。

bool is_factor(long long int num, long long int factor)
{
    if(!(num%factor))
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool is_prime(long long int num)
{
    long long int i;
    bool flag = true;
    for(i = 2; i <= num/2; i++)
    {
        if(!(num%i))
        {
            flag = false;
        }
    }
    return flag;
}

int main(void)
{
    long long int i, max_factor = 1;
    for(i = 1; i < 600851475143; i++)
    {
        if(is_factor(600851475143,i) && is_prime(i) && i>max_factor)
        {
            max_factor = i;
        }
    }
    printf("%d\n",max_factor);
    return 0;
}

Answer 1

到目前为止，在高层次上，您使用的总体策略如下：
试着把目标数除以所有小于或等于目标数一半的数。
每次你找到一个除数，看看它是一个素数，大于最大的因素。如果是，更新最大因子。
以这种方式返回最大的数字。
考虑到你的目标是找出单个数字中最大的因素，这是一个相当合理的策略有几种方法可以加快速度。其中一些在评论中得到了回应，而另一些（据我所知）并没有在那里提出。
优化1：消除素性检查
现在，你要把目标数除以每个可能的除数，然后检查这些除数是否是素数。如果你的目标数有很多除数，那么你会花很多时间检查不是素数的除数，这会消耗你的运行时间。
另一种方法如下。如前所述，尝试将目标数按顺序除以每个可能的除数。但是，做一个改变：每当你找到一个除数，通过尽可能多的除数来修改目标数如果你这样做，就会发生一些有趣的事情：你将发现除这个数的唯一数字就是素数。
这是为什么？
想知道为什么，想想这会怎样你将首先测试2是否除以这个数如果是这样的话，你会尽可能多地把2的副本除掉，这意味着如果你试着在以后除以2的倍数，你会发现较大的数字不是除数。
类似地，您将测试3是否除以数字。如果是这样的话，你将把3的所有副本都除掉，所以没有一个是3的倍数的数字会除掉剩下的数字。
这一次更改消除了对is_prime函数的需要，节省了大量工作。另外，你可以保证任何你这样找到的除数都是质数。
优化二：早停
只要候选除数大于目标数的一半，当前代码就停止搜索除数。如果你在寻找除数，这是你能做的最好的。但是，如果您开始进行上述优化，则可以提前停止。
上面的策略是把你遇到的所有主要因素一分为二，这样做还有一个额外的好处。假设，在完成所有的除法之后，剩下的目标数是n。现在，假设你的当前除数是d并且dn如果d除以n，则可以将n写成两个数d和n / d的乘积。因为你已经将目标数除以你遇到的所有素数，我们保证n没有小于d的素数。这意味着，反过来，如果n / dd，那么d不能是n的除数。为什么？因为，如果d真的除以n，那么这个数就必须有一个小于n / d的素因子，但是我们知道d没有这样的素因子。
因此，在尝试除数时，可以在n<n / d时立即停止，或者等效地，在d<n2时立即停止。一旦发生这种情况，你就会知道d不再有任何小于自身的素数因子，所以剩余的数n是最后一个素数因子。
实际上，这将极大地加快速度。你的目标数大约是1012，只要最后一个除数大约在这个数的平方根的顺序上，也就是106左右，你就可以停止。这意味着你只需要搜索一百万个除数，而不是一万亿个！
优化三：智能选择除数
以上两个优化或多或少地反映了你最初的策略，可能足以让你得到你的答案，并称之为一天然而，如果你想让事情变得更快一点只是为了好玩，你可以考虑选择你的除数更好一点。
例如，现在，你试图除以目标的数字有一半是偶数。除了2，没有偶数是素数，所以可以考虑将循环分成两部分：处理2的特殊情况，以及从3开始计数并采取2（3、5、7、9、11、13等）而不是1的步骤的循环。（盯着目标数字看，你会发现它不是偶数，所以你甚至可以完全跳过2的除法！）
更好的是，考虑下载所有质数的列表，直到大约107。要么硬代码列表到您的程序中，要么将其全部转储到一个文本文件中，并在程序启动时将其读入。然后，只将目标除以列表上的数字。喂你现在只需要除以素数，省时省力。（质数定理说，只有LN107≈18.4个小于107的数才是质数，所以这很可能会给你额外的20倍的加速比。
希望这有帮助！