#include int is_prime(unsigned long long n) { static unsigned long long i; for(i = 2; i * i <> n + 1; i++) if(n % i == 0) return 0; return 1; } unsigned long long biggest_prime_factor(unsigned long long n) { unsigned int p = 1; while(n > 1) { p++; if(is_prime(n)) return n; while(n % p == 0) n /= p; } return p; } int main() { unsigned long long a = 600851475143; printf(%llu, biggest_prime_factor(a)); return 0; } 因为因数总是配对的，比如 20 = 2 * 10 = 4 * 5，那么最大质因数肯定有一个小的因数与它配对，也就是说如果去掉前面的小因数后，剩下的是质数，那么这个质数就是所要找的最大质因数。 其中 is_prime 是为了加速当 n 不是两个大质数的乘积的情况，其复杂度为 。而如果 n 是两个大质数的乘积，反而起了反作用。 所以应该直接 unsigned long long biggest_prime_factor(unsigned long long n) { unsigned long long p = 1; while(n > 1) { p++; while(n % p == 0) n /= p; } return p; } 这样 文章来源:https://www.zhihu.com/question/417835312
