PROJECT EULER SOLUTION # 73

PROJECT EULER QUESTION # 73

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 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d <= 12,000?

PROJECT EULER SOLUTION # 73

package pe73;

import java.util.LinkedList;

public class pe73

{

      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=12000;

            long answer=0;

            System.out.println("started");

           

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

            LinkedList lst=new LinkedList();

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

            {

                  if(i%100==0)

                        System.out.println(i/100);

                 

                  boolean coPrimeArray[]=new boolean[i];

                  lst.add(coPrimeArray);

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

                        {

                              if(Fraction.hcf(i, j)==1)

                                    coPrimeArray[j]=true;

                        }

            }

            System.out.println("completed");

           

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

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

            {

                  if(i%100==0)

                        System.out.println(i/100);

                 

                  boolean coPrimeArray[]=(boolean[])(lst.get(i-1));

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

                        if(coPrimeArray[j])

                        {

                              Fraction f=new Fraction(j,i);

                              if(Fraction.compare(new Fraction(1,2),f)==1 && Fraction.compare(f, new Fraction(1,3))==1)

                              {

                                    //System.out.println(f);

                                    answer++;

                              }

                        }

            }

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

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

      }

}

Fraction.java

package pe73;

public class Fraction

{

      public long n,d;

      public Fraction(long n,long d)

      {

            this.n=n;

            this.d=d;

            simplifyFraction();

      }

     

      public void simplifyFraction()

      {

            long h=hcf(Math.abs(n),Math.abs(d));

            n/=h;

            d/=h;

            if(d<0 && n<0)

            {

                  d=-d;

                  n=-n;

            }

      }

     

      public static long hcf(long a,long b)

      {

            if(b==0)

                  return a;

            return hcf(b,a%b);

      }

     

      public static long lcm(long a,long b)

      {

            return (a*b)/hcf(a,b);

      }

     

      public boolean equals(Fraction f)

      {

            if((this.n==f.n && f.n==0) || (this.n==f.n && this.d==f.d))

                  return true;

            return false;

      }

     

      public static int compare(Fraction a,Fraction b)

      {

            long l=lcm(a.d,b.d);

           

            if((l/a.d * a.n) > (l/b.d * b.n))

                  return 1;

            else if((l/a.d * a.n) == (l/b.d * b.n))

                  return 0;

            else

                  return -1;

      }

      public String toString()

      {

            return this.n+"/"+this.d;

      }

}