【欧拉计划第 3 题】Largest prime factor
【摘要】 Problem 3The prime factors of 13195 are 5, 7, 13 and 29.What is the largest prime factor of the number 600851475143 ? 问题 313195 的质因数是 5、7、13 和 29。数字 600851475143 的最大质因数是多少? 思路分析首先要理解清楚质因数的概念质因数,在数...
Problem 3
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
参考资料:
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)