PROJECT EULER SOLUTION # 72

PROJECT EULER QUESTION 72

Consider the fraction, n/d, where n and d are positive integers. If nd and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d  8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 21 elements in this set.

How many elements would be contained in the set of reduced proper fractions for d  1,000,000?

PROJECT EULER SOLUTION 72

package pe72;

import java.util.LinkedList;

public class pe72

{

      public static boolean isPrime(long n)

      {

            for(int i=2;i<=(int)Math.sqrt(n);i++)

            {

                  if(n%i!=0)

                        return false;

            }

            return true;

      }

      public static void main(String args[])

      {

            long start=System.currentTimeMillis();

            int num=1000000;

            System.out.println("started pe 72");

           

            /***********************/

            LinkedList lst[]=new LinkedList[num+1];

            for(int i=0;i<lst.length;i++)

                  lst[i]=new LinkedList<String>();

            boolean primes[]=new boolean[num+1];

            for(int i=2;i<=num;i++)

                  if(!primes[i])

                        for(int j=i;j<=num;j+=i)

                        {

                              primes[j]=true;

                              lst[j].add(""+i);

                        }

            System.out.println("completed");

           

            /***********************/

            /*

            for(int i=2;i<=num;i++)

            {

                  System.out.print("i = "+i+" = ");

                  for(int j=0;j<lst[i].size();j++)

                  {

                        System.out.print(" "+Integer.parseInt(lst[i].get(j)+""));

                  }

                  System.out.println();

                 

            }

            */

            long answer=0;

            for(int i=2;i<=num;i++)

            {

                  long temp=i;

                  for(int j=0;j<lst[i].size();j++)

                  {

                        int t=Integer.parseInt(lst[i].get(j)+"");

                        temp=(temp*(t-1))/t;

                  }

                  answer+=temp;

            }

            System.out.println("Answer = "+answer);

            System.out.println("Execution time = "+(System.currentTimeMillis()-start)/1000.0);

      }

}