【 Project Euler | 欧拉计划】Problem1~5 c++详解+答案

目录

Problem1 3或5的倍数

-原题(翻译来自pe-cn.github.io 下同)

英语原题
中文翻译
Multiples of 3 and 5
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3,5,6 and 9.The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

3或5的倍数
在小于10的自然数中,3或5的倍数有3、5、6和9,这些数之和是23。

小于1000的自然数中所有35的倍数之和。

-思路

没啥好说的 就是枚举

-代码

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
	int sum=0;//统计总和
	for(int i=1;i<1000;i++)//枚举1到1000 看看每个数是否符合要求
	{
		if(i%3==0||i%5==0) sum+=i;//如果符合 总和加上当前数
	}
	cout<<sum;//输出
}

-答案

233168

Problem2 偶斐波那契数

-原题

英语原题
中文翻译
Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ···

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

偶斐波那契数
在小于10的自然数中,3或5的倍数有3、5、6和9,这些数之和是23。

斐波那契数列中的每一项都是前两项的和。由和开始生成的斐波那契数列的前项为:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ···

考虑该斐波那契数列中不超过四百万的项,求其中为偶数的项之和。

-思路

把从1到4000000之间的斐波那契数列每一项算出来 然后把其中的偶数累加

-代码

#include<cstdio>
#include<iostream>
using namespace std;
int a[100086];//储存斐波那契数列
int main()
{
	a[1]=1;//数列的第一项为1
	a[2]=2;//数列的第二项为2
	int sum=2;//偶数之和 由于前两项不在循环中 所以先要计入2
	for(int i=3;a[i-1]<=4000000;i++)//若数列的前一值不大于4000000 则继续判断当前值 否则结束循环
	{
		a[i]=a[i-1]+a[i-2];//当前值为前两项之和
		if(a[i]%2==0) sum+=a[i];//如果为偶数则计入
	}
	cout<<sum;//输出
	return 0;
}

-答案

4613732

Problem3 最大质因数

-原题

英语原题
中文翻译
Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

最大质因数
13195的质因数包括5、7、13和29。

600851475143的最大质因数是多少?

-思路

由于任何合数都能分解成一个质数和另一个数,所以我们可以把600851475143分解成一个尽量小质数和一个合数,然后继续分解该合数,直到分解出两个质数,即无法继续分解,此时取最后分解成的两个质数中较大的一个

-代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
bool su(long long a)//判断质数的函数
{
	int s=sqrt(a);
	for(int i=2;i<=s;i++)
		if(a%i==0) return 0;
	return 1;
}
int main()
{
	long long a=600851475143;
	for(int i=2;;i++)//枚举分解的质数 由于任何自然数都能被1整除 所以从2开始向上枚举
	//关于为什么不用判断i是否为质数:若i为合数且能将a整除 那么在i前面出现的i的质因子肯定能将a整除 进行分解后i就会重置为2 所以只要i为合数 就不会执行if中的内容
	{
		if(a%i==0)//若a可以被i整除 就分解成i和a/i
		{
			a/=i;//将a/i继续向下分解
			i=2;//重置i 继续从2开始枚举
		}
		if(su(a))//若i和a/i同时为质数 则取答案
		{
			cout<<a;
			break;
		}
	}
	return 0;
}

-答案

6857

Problem4 最大回文乘积

-原题

英语原题
中文翻译
Largest palindrome product
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

最大回文乘积
回文数就是从前往后读和从后往前读都一样的数。由两个2位数相乘得到的最大的回文数是9009 = 91 × 99。

求由两个3位数相乘得到的最大的回文数。

-思路

枚举所有乘积→取出所有回文数→取其中最大的

-代码

#include<cstdio>
#include<iostream>
using namespace std;
int sa[7];//将乘积按位存放 方便判断回文
bool hui(int a)//判断是否回文的函数
{
	int idx=0;//求乘积的位数
	while(a>0)//将a的个位放入sa[1] 十位放入sa[2] 以此类推
	{
		sa[++idx]=a%10;
		a/=10;	
	}
	if(sa[1]==sa[idx]&&sa[2]==sa[idx-1]&&sa[3]==sa[idx-2])//如果回文
	//注:由于两个三位数的乘积必定为5位数或6位数 所以可以在一个if中判断 否则要用循环
		return 1;
	return 0;	
}
int main()
{
	int ans;
	for(int i=999;i>=100;i--)//枚举第一个三位数
	{
		for(int j=999;j>=100;j--)//枚举第二个三位数
		{
			int a=i*j;//乘积
			if(hui(a)) //如果回文
			{
				ans=max(ans,a);//比较ans中当前存放的最大回文值和本次求出来的回文值 将较大的存入ans
				continue;
			}
		}
	}
	cout<<ans;//输出
	return 0;
}

-答案

906609

Problem5 最小公倍数

-原题

英语原题
中文翻译
Smallest multiple
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

最小公倍数
2520是最小的能够被1到10整除的数。

最小的能够被1到20整除的正数是多少?

-思路

将1~20之间的所有数分解为ab * cd *···然后将这些数乘起来 我们可以得到:

1*2*3*22*5*2*3*7*23*32*2*5*11*22*3*13*2*7*3*5*24*17*2*32*19*22*5

由于要求的数能被1~20中的任意一个整除 所以此时我们的目标变成了求能被上面算式中的任意一项整除的数中最小的
由于只要一个数能被ab整除就能被ac整除(b>c) 所以对于上面的算式相同底数的任意两项 我们只需要保留指数较大的一项 指数和底数都相同的两项只需保留一项 (去重) 得到的算式为

1*5*7*11*13*24*17*32*19

我们此时仍然要求能被上面算式中的任意一项整除的数中最小的 此时答案即为算式结果
本题的求解方法其实就是约分 只不过看着更nb 只不过更好理解(?
我是后来才明白这是约分的 但是敲都敲完了……

-代码

无代码 按计算器

-答案

232792560

上一篇:欧拉函数板子题


下一篇:P2568 GCD(欧拉函数)