Project Euler——Problem 5 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
Project Euler——Problem 4
Project Euler——Problem 6

Project Euler——Problem 5

daybreakcx posted @ 2009年7月14日 01:43 in Prject Euler , 1734 阅读

原题与答案：

Problem 5

30 November 2001

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 number that is evenly divisible by all of the numbers from 1 to 20?

Answer:232792560

 

分析与解答：

本题求可以被1到20整除的最小的数是多少，这个根据数论性质可以很容易得出，我是笔算得到的结果，题目可以转化为求1到20的最小公倍数，这个问题有一种求法是利用求最大公约数得到：两个数的最小公倍数等于他们的乘积除以他们的最大公约数，而最大公约数可以利用辗转相除法轻松得到，但是这样对于像20这样的小数值未免有点浪费，于是可以用另一个知识：假设a质因数分解是a=p_1^{s_1}*p_2^{s_2}*...*p_k^{s_k}，b的质因数分解是b=p_1^{t_1}*p_2^{t_2}*...*p_k^{t_k}，实际中两个数的质因数集合不一定相同，我们对于a有而b没有的质因数p_i设置t_i=0，对于b有而a没有的质因数p_j设置s_j=0，那么我们可以得到a和b的最小公倍数s=p_1^{max(s_1,t_1)}*p_2^{max(s_2,t_2)}*...*p_k^{max(s_k,t_k)}，利用这条性质我们只要求出每个小等于20的质数的可能得到的最大次数即可，具体实现见源代码：

 

  1. #include<stdio.h>
  2. int plist[8]={2,3,5,7,11,13,17,19},s=20,ans=1,i,t;
  3. int main()
  4. {
  5.         for (i=0;i<8;i++)
  6.         {
  7.                 t=1;
  8.                 while (t<=s) t*=plist[i];
  9.                 ans*=t/plist[i];
  10.         }
  11.         printf("%d\n",ans);
  12.         return 0;
  13. }

 

 

Small_feed 评论 (2)
1
[回复]
== 说:
2010年7月27日 04:28

呃，在http://whitedeath.is-programmer.com/posts/18075.html看到另一种解法。。。
ans = 1 * 16 * 9 * 5 * 7 * 11 * 13 * 17 * 19;

2
[回复]
Avatar_small
daybreakcx 说:
2011年1月27日 03:36

其实你有没有考虑过那些数怎么得来的呢
16=2^3
9=3^2
实际上还是20以内的素数而已，那文章我看过了，它将某些部分直接给了结果，实际上方法用的是一样的，都要保证各个素数的次数是1到20中的最大值，呵呵:)


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter