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);
}
}
No comments:
Post a Comment