Problem 3
Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
最大质因数
13195的所有质因数为5、7、13和29。
600851475143最大的质因数是多少？
题目解答
朴素解法：暴力枚举（枚举所有因子并判断是否为素数即可）
优化算法：
在这里我们可以利用 算术基本定理 来解决这个问题。
算术基本定理：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。
遇到的素数不断分解即可，直到分解到1时退出，我们的数字是从小到大遍历的，所以最后分解到一时的素因子一定时最大的。
题目代码
#include <stdio.h>
#include <inttypes.h>
#define N 600851475143
int main(){int32_t ans;int64_t temp = N;for (int32_t i=2;;i++){if (temp % i == 0){while (temp % i == 0){temp /= i;}ans = i;if(temp == 1){break;}}}printf("%" PRId32 "\n",ans);
}