这是我的code的下问题＃3，从项目欧拉，在那里我有找到600851475143最大的主要因素。

here is my code in C for problem#3 from project-Euler, where I have to find the largest prime factor of 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的code返回0，这显然是错误的。 谁能帮助吗？ 非常感谢。

Although it works fine for small numbers, gradually it takes more and more time for it to give an answer. And, finally, for 600851475143 the code returns 0, which is obviously wrong. Could anyone help? thanks a lot.

推荐答案

有几件事情需要考虑：

由于@Alex雷诺兹指出的那样，你想因子的数量可能是如此之大，不适合在 INT 。您可能需要使用长或 uint64_t中存储号码。这本身就可以解决这个问题。

As @Alex Reynolds pointed out, the number you're trying to factor might be so large that it can't fit in an int. You may need to use a long or a uint64_t to store the number. That alone might solve the problem.

而不是检查每一个除数，看哪些是素数，则可能反而想尝试这个办法：将n设置为600851475143.对于每一个整数2向上，尝试除以n乘该整数。如果干净划分出来，然后分出来这个数字的所有副本从n和记录最大素因子作为当前的整数。如果你仔细想想一点，你会发现，你会考虑这种方式唯一的除数是质数。作为一个有用的提示 - 如果n没有除数（除了1以外）小于＆拉迪奇; N，那么它的素数。这可能有助于给你一个上限的搜索空间，它比除以你使用的两大绝招严格得多。

Rather than checking each divisor and seeing which ones are prime, you might instead want to try this approach: set n to 600851475143. For each integer from 2 upward, try dividing n by that integer. If it cleanly divides out, then divide out all copies of that number from n and record the largest prime factor as being the current integer. If you think about it a bit, you'll notice that the only divisors you'll consider this way are prime numbers. As a helpful hint - if n has no divisors (other than 1) less than √n, then it's prime. That might help give you an upper bound on your search space that's much tighter than the division by two trick you're using.

，而不是增加一个除数，尝试测试出2作为除数，然后只由奇数除以（3，5，7，9，11，等等）否偶数比其他2是素，所以这个半号的数目需要除以

Rather than increasing the divisor by one, try testing out 2 as a divisor and then only dividing by odd numbers (3, 5, 7, 9, 11, etc.) No even number other than 2 is prime, so this halves the number of numbers you need to divide by.

另外，创建一个文件中存储的所有素数达＆拉迪奇。 ： - ）

Alternatively, create a file storing all prime numbers up to √600851475143 by downloading a list of primes from the internet, then just test each one to see if any of them divide 600851475143 and take the biggest. :-)

希望这有助于！