Sunday, 2 November 2014

PROJECT EULER SOLUTION # 72

PROJECT EULER QUESTION 72
Consider the fraction, n/d, where n and d are positive integers. If n<d 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);
      }
}


No comments:

Post a Comment