Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!

Project Euler——Problem 9

原题与答案：

Problem 9

25 January 2002

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a^(2) + b^(2) = c^(2)

For example, 3^(2) + 4^(2) = 9 + 16 = 25 = 5^(2).

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Answer:31875000

 

分析与解答：

这个题目是求一组互不相等的勾股数使得他们的和为1000，求他们的乘积。直接的想法就是直接枚举，当然排除掉不可能的情况后就很快可以得到结果了，下面是程序源代码：

 

  1. #include<stdio.h>
  2. int a,b,c;
  3. bool yet;
  4. int main()
  5. {
  6.         yet=false;
  7.         for (a=1;a<=332;a++)
  8.         {
  9.                 for (b=a+1;!yet&&a+b+b+1<=1000;b++)
  10.                         if (a*a+b*b==(1000-a-b)*(1000-a-b))
  11.                         {
  12.                                 yet=true;
  13.                                 break;
  14.                         }
  15.                 if (yet) break;
  16.         }
  17.         printf("%d\n",a*b*(1000-a-b));
  18.         return 0;
  19. }

 

 

Prject Euler Comments(0) 2009年7月17日 21:42

Project Euler——Problem 8

原题与答案：

Problem 8

11 January 2002

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Answer:40824

 

分析与解答：

题目的意思是对于1000位数值求出连续五位的最大乘积，这个题目不用多说了，直接用程序枚举，然后出结果，源程序代码如下：

 

  1. #include<stdio.h>
  2. char str[1002]="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
  3. int s,i,ans;
  4. int main()
  5. {
  6.         ans=-1;
  7.         for (i=0;str[i+5];i++)
  8.         {
  9.                 s=(str[i]-'0')*(str[i+1]-'0')*(str[i+2]-'0')*(str[i+3]-'0')*(str[i+4]-'0');
  10.                 if (s>ans) ans=s;
  11.         }
  12.         printf("%d\n",ans);
  13.         return 0;
  14. }

 

 

Prject Euler Comments(0) 2009年7月17日 21:35

Project Euler——Problem 7

原题与答案：

Problem 7

28 December 2001

 By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^(th) prime is 13.

What is the 10001^(st) prime number?

Answer:104743

 

分析与解答：

这个题目笔算我是没办法了，但是用程序可以很快得到，有一种思路是用试除，但是试除到了后期会有大量的取余运算，时间消耗会不断增长，我写过程序尝试的效果并不是很好，最后决定贴出用筛法做的，基本上结果是瞬出，当然这个数值我曾经做过估计，最早我是用了1000000，结果没想到在110000都不到的时候就出了结果，于是我的程序里面是160000的界，平方也好开。源程序代码如下：

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. const int RANGE=160000;
  4. const int SQRTRANGE=400;
  5. bool nprime[RANGE+1];
  6. int cnt=0,i,j;
  7. int main()
  8. {
  9.         memset(nprime,false,sizeof(nprime));
  10.         for (i=2;i<RANGE;i++)
  11.                 if (!nprime[i])
  12.                 {
  13.                         cnt++;
  14.                         if (cnt==10001) break;
  15.                         if (i<=SQRTRANGE)
  16.                                 for (j=i*i;j<RANGE;j+=i)
  17.                                         nprime[j]=true;
  18.                 }
  19.         printf("%d\n",i);
  20.         return 0;
  21. }

 

 

 

 

Prject Euler Comments(0) 2009年7月17日 21:27

Project Euler——Problem 6

原题与答案：

Problem 6

14 December 2001

The sum of the squares of the first ten natural numbers is,

1^(2) + 2^(2) + ... + 10^(2) = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)^(2) = 55^(2) = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Answer:25164150

 

分析与解答：

这个题目是求1到100的和平方与平方和的差，我们可以很容易地利用求出通项公式。首先是和平方：(1+2+...+n)^2=[\dfrac{n*(n+1)}{2}]^2=\dfrac{n^2*(n+1)^2}{4}，然后是平方和：1^2+2^2+...+n^2=\dfrac{n*(n+1)*(2*n+1)}{6}，最后是他们的差：(1+2+...+n)^2-(1^2+2^2+...+n^2)=\dfrac{n^2*(n+1)^2}{4}-\dfrac{n*(n+1)*(2*n+1)}{6}=\dfrac{n*(n+1)*(n-1)*(3*n+2)}{12}。于是带入公式就可以得到结果，当然用程序这个题目也是很容易实现的，源代码如下所示：

 

  1. #include<stdio.h>
  2. int res=0,i;
  3. int main()
  4. {
  5.         for (i=1;i<=100;i++)
  6.                 res+=i;
  7.         res*=res;
  8.         for (i=1;i<=100;i++)
  9.                 res-=i*i;
  10.         printf("%d\n",res);
  11.         return 0;
  12. }

 

 

Prject Euler Comments(4) 2009年7月17日 20:57

Project Euler——Problem 5

原题与答案：

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. }

 

 

Prject Euler Comments(2) 2009年7月14日 01:43

Project Euler——Problem 4

原题与答案：

Problem 4

16 November 2001

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.

Answer:906609

 

分析与解答：

这个题目也是很简单的，题目求两个三位数，使得他们的乘积是回文数，要求返回最大的满足条件的回文数，这里只需要枚举每对三位数，并且对他们的乘积进行判定输出最大值即可，编码没有什么难度，以下是实现代码：

 

  1. #include<stdio.h>
  2. int num[10],ans,i,j,s;
  3. bool ispalindrome(int s)
  4. {
  5.         int i,j;
  6.         num[0]=0;
  7.         while (s)
  8.         {
  9.                 num[++num[0]]=s%10;
  10.                 s/=10;
  11.         }
  12.         for (i=1,j=num[0];i<j;i++,j--)
  13.                 if (num[i]!=num[j]) return false;
  14.         return true;
  15. }
  16. int main()
  17. {
  18.         ans=0;
  19.         for (i=100;i<=999;i++)
  20.                 for (j=i;j<=999;j++)
  21.                 {
  22.                         s=i*j;
  23.                         if (s>ans&&ispalindrome(s)) ans=s;
  24.                 }
  25.         printf("%d\n",ans);
  26.         return 0;
  27. }

 

 

Prject Euler Comments(0) 2009年7月14日 01:36

Project Euler——Problem 3

原题与答案：

Problem 3

02 November 2001

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Answer:6857

 

分析与解答：

题目的大意是求600851475143的最大质因子，这个问题的解决也很容易，只要将每个因子都试除从中取出最大的即可，但是要注意的是，如果单独去一个个试除的话，必然会导致运算的时间非常的久，我们考虑只需要计算到\sqrt{600851475143}=775146即可，因为如果有素因子大于这个数，那么通过对于小等于775146的素数的试除，剩下的数值一定是一个素数。所以我们可以一边利用筛法进行素数生成，一边进行试除将原来的数值变小，在C中这个题目的数值记录要用到64位整数，具体实现代码如下：

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. long long s,i,j,ans;
  4. bool nprime[775147];
  5. int main()
  6. {
  7.         s=600851475143LL;
  8.         memset(nprime,false,sizeof(nprime));
  9.         for (i=2;i<=775146;i++)
  10.                 if (!nprime[i])
  11.                 {
  12.                         if (s%i==0) ans=i;
  13.                         while (s%i==0) s/=i;
  14.                         if (s==1) break;
  15.                         for (j=i*i;j<=775146;j+=i) nprime[j]=true;
  16.                 }
  17.         if (s!=1) ans=s;
  18.         printf("%lld\n",ans);
  19.         return 0;
  20. }

 

 

Prject Euler Comments(0) 2009年7月14日 01:23

Project Euler——Problem 2

原题与答案：

Problem 2

19 October 2001

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, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Answer:4613732

 

分析与解答：

这个题目也是简单的模拟，即求不超过4000000的偶数斐波那契数列项的和，笔算我没想到好方法，直接给出程序的运算方法吧：

 

  1. #include<stdio.h>
  2. int sum=2,a=1,b=2,i;
  3. int main()
  4. {
  5.         for (i=3;;i++)
  6.                 if (i&1)
  7.                 {
  8.                         a+=b;
  9.                         if (a>4000000) break;
  10.                         if (!(a&1)) sum+=a;
  11.                 }
  12.                 else
  13.                 {
  14.                         b+=a;
  15.                         if (b>4000000) break;
  16.                         if (!(b&1)) sum+=b;
  17.                 }
  18.         printf("%d\n",sum);
  19.         return 0;
  20. }

 

 

Prject Euler Comments(0) 2009年7月14日 00:33

Project Euler——Problem 1

原题与答案：

Problem 1

05 October 2001

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.

Answer:233168

 

分析与解答：

这个题目描述很简单，是求小于1000的所有3或者5的倍数的和，第一个题就是a+b性质的，很容易过，刚开始我直接利用容斥原理笔算求出了结果。首先是小于1000的3倍数的和 sum1=3+6+...+999=(3+999)*(999/3)/2=166833，接着是小于1000的5倍数的和sum2=5+10+...+995=(5+995)*(995/5)/2=99500，最后是小于1000的15的倍数sum3=15+30+...+990=(15+990)*(990/15)/2=33165。于是我们要的结果sum=sum1+sum2-sum3=166833+99500-33165=233168。

当然，这个题目用C写一下也不难，很容易就可以得到代码：

  1. #include<stdio.h>
  2. int i,sum;
  3. int main()
  4. {
  5.         sum=0;
  6.         for (i=1;i<1000;i++)
  7.                 if (i%3==0||i%5==0) sum+=i;
  8.         printf("%d\n",sum);
  9.         return 0;
  10. }

 

 

Prject Euler Comments(0) 2009年7月14日 00:10

发现一个好玩的地方

临近领取毕业证书，闲来无事在网上闲逛，发现一个不错的地方，叫做Project Euler。这上面不要求提交代码，只要求给出答案，以数学题偏多，用了点时间把第一版的50题按照顺序给刷掉了，感觉很不错。

原先有人给我提及过这个题库，当时没太在意，现在看看决定坚持做下去，数学题平时没事干可以练习一下思维，此外可以在上面练习高精度和数论等具体知识，准备在这上面写相应的解题报告，仅作记录。

差点忘记说了，这个题库的地址是http://projecteuler.net/，注册一个帐号就可以做了，每过一题就可以得到一个勾，然后可以看到世界上其他人的解答，突然发现很多高人，有人用汇编A掉了不少题目，用python等的也不少，因为可以用来方便进行大数值计算，但我还是决定完全用C来进行解题。

Prject Euler Comments(0) 2009年7月13日 22:18