c - 有关如何使我的算法更快的建议

这是我在欧拉项目问题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向上的每个整数，尝试将n除以该整数。如果它清楚地被除掉，那么将该数字的所有副本从n中除掉，并将最大素因子记录为当前整数。如果你稍微考虑一下，你会注意到你用这种方法考虑的唯一除数是素数。作为一个有用的提示-如果n没有小于√n的除数（除了1），那么它就是素数。这可能有助于给你的搜索空间一个上限，比你使用的两个技巧的划分要紧得多。
与其把除数增加一，不如试着把2作为除数，然后只除以奇数（3、5、7、9、11等），除了2以外，没有任何偶数是素数，所以这将需要除以的数减半。
或者，通过从互联网下载素数列表，创建一个文件来存储所有小于等于√600851475143的素数，然后测试每个素数，看看它们中是否有一个除以600851475143，取最大的：-）
希望这有帮助！