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 ?
问题 3 最大质因数
13195 的质因数是 5、7、13 和 29。
数字 600851475143 的最大质因数是多少？
思路分析
首先要理解清楚质因数的概念
质因数，在数论中是指能整除给定正整数的质数。除了1以外，两个没有其他共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质
正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。根据算术基本定理，任何正整数皆有独一无二的质因子分解式。只有一个质因子的正整数为质数
如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数，并且这个因数一定是一个质数
每个合数都可以写成几个质数相乘的形式，这几个质数均称为该合数的质因数
例如：6 的质因子是 2 和 3（6 = 2 × 3）；10 的质因子是 2 和 5（10 = 2 × 5）
求解质因数的方法中，比较常见的事短除法，它的具体求解步骤是
- N/2 （N为任意大于 2 的自然数），得到商
- 步骤一的商继续除以 2，直到商不能被 2 整除
- 被除数加一，比较平方数是否小于被除数（若小于，则所得商继续除以 3，不能整除，则除以 5）
- 分层循环，当除数的平方大于等于被除数时退出循环，此时 N 为最大质因数。一层判断除数的平方是否小于被除数，另一层判断被除数是否可以整除除数
代码实现
整体思路并没有问题，但是由于题目中给定数值已经超过了一般的执行范围，总是报错 stackoverflow，并未计算到最终结果，或许可以考虑用一台性能更好的机器测试下
该 C++ 版本代码编译速度很快，供参考
#include <stdio.h> #include <math.h> #include <limits> using namespace std; typedef int INT; typedef char CHAR; typedef void VOID; typedef double DOUBLE; #define PRINT printf #define DPRINT printf DOUBLE MaxPrimeFactor(DOUBLE n) { DOUBLE i; DOUBLE tem; DOUBLE max; if(n - 1.99999999999999 < numeric_limits<DOUBLE>::epsilon()) return -1.0; max = n; tem = n / 2.0; while(fabs(tem - (floor(tem))) < numeric_limits<DOUBLE>::epsilon()) { DPRINT("prime factor is：%lf\n", 2.0); n = tem; tem = n / 2.0; } if(fabs(n-1.0) < numeric_limits<DOUBLE>::epsilon()) return 2.0; for(i=3.0; i<=max; i+=2.0) { if(fabs(n-i) < numeric_limits<DOUBLE>::epsilon()) { DPRINT("prime factor is：%lf\n", i); return i; } tem = n / i; while(fabs(tem - (floor(tem)) < numeric_limits<DOUBLE>::epsilon())) { DPRINT("prime factor is：%lf\n", i); n = tem; tem = n / i; } if(fabs(n-1.0) < numeric_limits<DOUBLE>::epsilon()) return i; } return -1.0; } INT main(INT argc, CHAR *argv[]) { while(1) { PRINT("input num:\n"); DOUBLE n; scanf("%lf", &n); if(n < 0) break; DOUBLE res = MaxPrimeFactor(n); PRINT("The largest prime factor is：%lf\n", res); } return 0; }
答案：6857
