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 版本代码编译速度很快，供参考
代码语言：javascript复制#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：%lfn", 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：%lfn", i);
return i;
}
tem = n / i;
while(fabs(tem - (floor(tem)) < numeric_limits<DOUBLE>::epsilon()))
{
DPRINT("prime factor is：%lfn", 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：%lfn", res);
}
return 0;
}答案：6857
参考资料：
- Find the largest prime factor of a composite number
