首页 > 代码库 > ProjectEuler 005题

ProjectEuler 005题

2024-07-05 22:34:31   224人阅读

题目：

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?

此题就是求最小公倍数的，刚开始我考虑的太复杂，打算求出每个数的素数因子，然后去处一些共有的部分，后来突然想到了最小公倍数。

 1 #include<iostream>
 2 using namespace std;
 3 int getLeastCommonMultiple(int num1, int num2);
 4 int GetMaxCommonDivide(int num1, int num2);
 5 int main()
 6 { 
 7     int res = 20;
 8     for(int i = 19; i >=2; i--) {
 9         if( res % i == 0){
10             continue;
11         }
12         else {
13             res = getLeastCommonMultiple(res, i);
14         }
15     }
16     cout << res << endl;
17     system("pause");
18     return 0;
19 }
20 //求最小公倍数
21 int getLeastCommonMultiple(int num1, int num2) {
22     return num1*num2/(GetMaxCommonDivide( num1, num2));
23 }
24 /*  辗转相除法求最大公约数 */ 
25 int GetMaxCommonDivide(int num1, int num2) {
26     int temp;
27     while(num2!=0){
28         temp = num1%num2;
29         num1 = num2;
30         num2 = temp;
31     }
32     return num1;
33 }

 


联系
我们