【欧拉计划第 3 题】最大质因数 Largest prime factor

发表于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

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）

求解质因数的方法中，比较常见的事短除法，它的具体求解步骤是

  1. N/2 （N为任意大于 2 的自然数），得到商
  2. 步骤一的商继续除以 2，直到商不能被 2 整除
  3. 被除数加一，比较平方数是否小于被除数（若小于，则所得商继续除以 3，不能整除，则除以 5）
  4. 分层循环，当除数的平方大于等于被除数时退出循环，此时 N 为最大质因数。一层判断除数的平方是否小于被除数，另一层判断被除数是否可以整除除数

代码实现

整体思路并没有问题，但是由于题目中给定数值已经超过了一般的执行范围，总是报错 stackoverflow，并未计算到最终结果，或许可以考虑用一台性能更好的机器测试下

该 C++ 版本代码编译速度很快，供参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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

参考资料：

  • Find the largest prime factor of a composite number