Project Euler : 66–70

• Problem 67 ( Click to Read )

This is a harder version of problem 18. In problem 18, number of rows were only 15 but here 100. The algorithm does not need any change but the dimensions do. You can read strategy to solve problem 18 on this post of my blog.

#include <stdio.h>
int main()
{
  int a[100][100];
  int i, j, x;
 
  for (i=0; i<100; i++)
  {
    for (j=0; j<=i; j++)
    {
      scanf("%d", &a[i][j]);
    }
  }
  for (i=99; i>0; i--)
  {
    for (j=0; j<i; j++)
    {
      x = a[i][j] > a[i][j+1] ? a[i][j] : a[i][j+1];
      a[i-1][j] += x;
    }
  }
  printf("%d\n", a[0][0]);
  return 0;
}

• Problem 69 ( Click to Read )

This is one of those problems which I could not do without help from internet. Seems problem setter wanted solvers to do a little search and than come up with a strategy.

For the purpose of theory one should read this wiki link, it gives a general formula:

φ(n) = n * ∏ (1–1/p) , where p are primes which evenly divides n

which means n/φ(n) equals multiplications of p/(p-1). It can be manually checked that value of p/(p-1) decreases as p increases, so higher the ‘p’ lesser would be their contribution to increase n/φ(n). Also the more distinct p we have the higher would be product, so would not be good if ’n’ were only multiplications of few distinct small primes? Yes, done.

Find the multiplication of all prime numbers beginning with 2 until this multiplication is less than equal to 1000000. That would be n ;)

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