whitedeath's Blog

Project Euler 6~10

Problem 6

14 December 2001

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

1² + 2² + ... + 10² = 385

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

(1 + 2 + ... + 10)² = 55² = 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.

#include<stdio.h>
int main()
{
	int i;
	long long ans;
	
	ans = 0;
	for(i = 1;i <= 100;i++)
       ans += (i * i);
    
	ans = 5050 * 5050 - ans;
    
    printf("%lld\n",ans);
    
    return 0;
}

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?

#include<stdio.h>
#include<string.h>
#define Max 110000
int main()
{
    int a[Max+1];
    int temp,n,i,cnt;

    memset(a,0,sizeof(a)) ;
    a[0] = a[1] = 1;                       
    for (i = 2;i <= Max;i++)
    {
        if (a[i] == 0)
        {
            temp = 2 * i;                      
            while (temp <= Max)
            {
                a[temp] = 1;
                temp += i;
            }
        }
    }
   
    cnt = 0;
    for (i = 2;i <= Max;i++)
    {
	     if(a[i] == 0)
             cnt++;
         if(cnt == 10001)
           break;
	}
	
    printf("%d\n",i);
	
	return 0;
}

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

#include<iostream>
#include<string>
using namespace std;
string s = "73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450";
int main()
{
	int i,j,ans,max = -1;

	for(i = 0;i <= 996;i++)
	{
	   ans = 1;	 
	   for(j = i;j <= i + 4;j++)	
    	   ans *= (s[j] - '0');
    	   
	   if(ans > max) 
	       max = ans;  
	}
	
    cout << max <<endl;

    return 0;
}

Problem 9

25 January 2002

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

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

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

#include<stdio.h>
#define Max 1000
int main()
{
	int a,b;
	
	for(a = 1; a <= Max;a++)
	  for(b = a + 1;b <= Max;b++)
	  	 if(a * a + b * b == (Max - a - b) * (Max - a - b))
		    goto end;

end: printf("%d\n",a * b * (Max - a - b));
    
    return 0;
}

Problem 10

08 February 2002

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

#include<stdio.h>
#include<string.h>
#define Max 2000000
int main()
{
    int a[Max + 1];
    long temp,n,i;
	long long ans;

    memset(a,0,sizeof(a)) ;
    a[0] = a[1] = 1;                       
    for (i = 2;i <= Max;i++)
    {
        if (a[i] == 0)
        {
            temp = 2 * i;                      
            while (temp <= Max)
            {
                a[temp] = 1;
                temp += i;
            }
        }
    }
   
    ans = 0;
    for (i = 2;i < Max;i++)
	     if(a[i] == 0)
             ans += i;

    printf("%lld\n",ans);
	
	return 0;
}

Posted by whitedeath 2010年5月18日 07:17

Category: Project Euler Tag: 数论 ACM Comment: (136)

Project Euler 1-5

今天发现一个很好玩的网站：projecteuler.net/，都是我喜欢的数论题

处理数字，我最喜欢！

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.

#include<stdio.h>
int main()
{
 int i,ans;
 
 ans = 0;
 for(i = 3;i < 1000;i++)
    if(i % 3 == 0 || i % 5 == 0)
       ans += i; 
    printf("%d\n",ans);
    
    return 0;
}

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.

#include<stdio.h>
int main()
{
	long long n,t,tmp,ans;
	
	t = 1;
	n = 1;
	ans = 0;
	while(n <= 4000000)
	{
	   tmp = n;
	   n = n + t;
	   t = tmp;

	   if(n % 2 == 0)
	     ans += n;	
	}
	
	printf("%lld\n",ans);

    return 0;
}

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 ?

#include<stdio.h>
int main()
{
    long long num = 600851475143ll;
	int i = 2;
	
	while (num > 1)
	{
		while(num % i == 0)  num /= i;
		i++;
	}
	i--;
	printf("%d\n",i);
	return 0;
}

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.

#include<stdio.h>
int check(int n)
{
	if(back(n) == n)
	  return 1;
    return 0;
}

int back(int n)
{
	int t;
	
	t = 0;
	while(n != 0)
	{
		t = t * 10 + n % 10;
		n /= 10;
	}
	return t;
}


int main()
{
	int n,m,ans,max;
	
	max = -1;
	for(n = 100;n <= 999;n++)
       for(m = n;m <= 999;m++)
       {
       	  ans = m * n;
       	  if(check(ans) && ans > max)
       	     max = ans; 
       }
	printf("%d\n",max);   
       
    return 0;
}

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?

#include<stdio.h>
int main()
{
	int ans;
	
	ans = 1 * 16 * 9 * 5 * 7 * 11 * 13 * 17  * 19; 
	printf("%d\n",ans);

    return 0;
}

Posted by whitedeath 2010年5月18日 06:42

Category: Project Euler Tag: 数论 ACM Comment: (3)

Coding,coding,that's my life~