Project Euler : 1–5

Introduction : Project Euler gives you opportunity to satisfy your hunger to solve challenging Mathematics and Programming problems. Here I have described about the methods and codes that I’ve used to solve these problems on Project Euler.
The objective of this is to learn, so use this blog only as a reference and instead of copy pasting codes, try to learn and code yourself.

My current national rank on Project-Euler is #257

• Problem 1 ( Click to Read )

This is a very simple and direct problem which requires no coding. To manually solve it, add all the multiples of 3 and multiples of 5 below 1000. To remove the duplicate addition subtract from this summation, the sum of all multiples of 15 below 1000.

(3+6+9+…+999)+(5+10+15+….+995)-(15+30+45+….+990)

Using formula of Arithmatic Progression you can find result, no coding required.

• Problem 2 ( Click to Read )

The problem can be solved in less than 1 second even if you write brute force algorithm. There are approximately 50 elements in Fibonacci series less than Four Million. If we begin our series from 0,1,1,2,3,5,8,…. we notice that every third element is even. No further hint is required to solve this problem.

#include<stdio.h>
#define MAX 4000000
int dp[50] = {0};
int fib (int n)
{
  if (n == 0 || n == 1)
    return n;
  else
  {
    if (!dp[n-1])
      dp[n-1] = fib(n-1);
    if (!dp[n-2])
      dp[n-2] = fib(n-2);
    dp[n] = dp[n-1] + dp[n-2];
    return dp[n];
  }
}
int main()
{
  int i, j, ans, sum = 0;
  dp[0] = 0;
  dp[1] = 1;
  for (i=2; ;i++)
  {
    ans = fib(i);
 
    if (ans > MAX)
      break;
    else if (!(ans&1))
      sum += ans;
  }
  printf(“%d\n”,sum);
  return 0;
}

• Problem 3 ( Click to Read )

This problem can be solved using brute force factorization in less than a second.
To solve this i have stored an array of prime numbers below 10000. Starting from first prime, if it divides the number evenly we store it and update number as the quotient. the last prime that divides the number is required answer.

#include <stdio.h>
int a[1148] = {List of all primes below 10000};
int main()
{
  long long unsigned int n = 600851475143LL;
  int i = 0, ans;
  while (n > 1)
  {
    ans = a[i];
    if (n%ans == 0)
      n /= ans;
    else
      i++;
  }
  printf(“%d\n”,ans);
  return 0;
}

• Problem 4 ( Click to Read )

To solve this problem iterate your loop between the largest & smallest values achievable from product of two three digit numbers. for each number check if it is palindrome and if yes check if it is larger than previously calculated palindrome.

#include <stdio.h>
int palin(int n)
{
  int p = n, q = 0;
  while (n)
  {
    q = q * 10 + (n % 10);
    n /= 10;
  }
  if (p == q)
    return 1;
  else
    return 0;
}
int main()
{
  int i, j, n, x = 0;
  for (i=999; i>99; i — )
  {
    for (j=i; j>99; j — )
    {
      n = i * j;
      if (palin(n) && n > x)
        x = n;
    }
  }
  printf(“%d”,x);
  return 0;
}

• Problem 5 ( Click to Read )

Again a very simple problem which requires less than a second to come to conclusion that we have to find LCM of first 20 numbers and we are done. To find LCM of 20 numbers sounds tedious. I stored 20 numbers in an array and used, array[i]=LCM(array[i], array[i-1])
This way, 20th element of array contains LCM of all 20 numbers after one iteration.

#include<stdio.h>
long long int gcd (long long int a, long long int b)
{
  if (b % a == 0)
    return a;
  else
    return gcd(b % a, a);
}
int main()
{
  int i;
  long long int array[20] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
  for(i=1; i<20; i++)
    array[i] = (array[i] * array[i-1]) / gcd(array[i], array[i-1]);
  printf(“%d\n”, array[19]);
  return 0;
}

You can find more Project Euler solutions on my Project Euler Publication.