【欧拉计划第 3 题】Largest prime factor

攻城狮杰森 发表于 2022/04/11 15:48:29 2022/04/11
【摘要】 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)

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

  1. N/2 (N为任意大于 2 的自然数),得到商
  2. 步骤一的商继续除以 2,直到商不能被 2 整除
  3. 被除数加一,比较平方数是否小于被除数(若小于,则所得商继续除以 3,不能整除,则除以 5)
  4. 分层循环,当除数的平方大于等于被除数时退出循环,此时 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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。