关于如何使我的算法更快的建议

问题内容：

这是我在Project Euler中针对问题3的C代码，在这里我必须找到最大的素数600851475143。

#include <stdio.h>
#include <stdlib.h>

bool is_prime(long int number){
     long int j;
     for (j=2; j<=number/2; j++){
             if (number%j==0) return false;
             if (j==number/2) return true;
            }
    }

int main(){

     long int input;
     scanf("%d", &input);
     long int factor;
     int ans=0;

     for (factor=input/2; factor>1; factor--){
             if (input%factor==0 && is_prime(factor)) {
                     ans = factor;
                     break;
                    }
            }

     printf("%d\n", ans);
     system("pause");
     return 0;
    }

尽管它对于少量数字有效，但逐渐需要更多时间来给出答案。最后，对于600851475143，代码返回0，这显然是错误的。有人可以帮忙吗？非常感谢。

问题答案：

需要考虑的几件事：

正如@Alex Reynolds指出的那样，您尝试考虑的数字可能太大，以致于不能包含在中int。您可能需要使用long或uint64_t来存储数字。仅此一项就可以解决问题。
您可能想尝试这种方法，而不是检查每个除数，看看哪一个是质数，将n设置为600851475143。对于从2到2的每个整数，请尝试将n除以该整数。如果将其完全除掉，则从n中除掉该数字的所有副本，并将最大素数记录为当前整数。如果稍微考虑一下，您会注意到，您将以这种方式考虑的唯一除数是质数。一个有用的提示-如果n的除数（除1外）不小于√n，则为质数。这可能会帮助您在搜索空间上设置一个上限，该上限比您正在使用的两个技巧的除法要严格得多。
而不是将除数增加1，请尝试将2作为除数进行测试，然后仅除以奇数（3、5、7、9、11等）。除2以外的偶数都不是质数，因此将数字减半您需要除以的数字。

或者，通过从互联网上下载素数列表来创建一个文件，以存储最多√600851475143的素数，然后仅测试每个素数以查看其中是否除以600851475143并取最大数。:-)

希望这可以帮助！

关于如何使我的算法更快的建议

微信关注