Problem 26: Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.
Wrote a brute force one which took a little over an hour to complete… much to my embarrassment (not posted).
Then, reading up on decimal expansion on wikipedia, refactored my original code to this.
import java.util.Vector;
class runner
{
private static int findRecurringLength(int d){
if( d<= 1) return 0;
int n = 1; int div = 0;
int result_length = 0;
while( true ){
int z = 1;
while( n < d ){
n *= 10;
z++;
}
div = n / d;
int divdigits = numOfDigits(div);
for(int i=divdigits+1;i0){
d/=10;
z++;
}
return z;
}
static Vector primestorage = new Vector();
private static boolean isPrime(int n){
double sqr = Math.sqrt(n)+1;
for(int i=0; i= sqr) break;
if(n % primestorage.get(i) == 0) return false;
}
primestorage.add(n);
return true;
}
public static void main (String[] args) throws java.lang.Exception
{
long time = System.currentTimeMillis();
primestorage.add(2);
int l = 0, llen = 0;
for(int d=2;d<1000;d++){
if(!isPrime(d)) continue;
int len = findRecurringLength(d);//2*d due to 1. len(period) <= d-1; 2. We need double the period to verify it.
if(llen < len){
llen = len; l=d;
}
}
System.out.println(l+" len:"+llen);
System.out.println("time: "+(System.currentTimeMillis() - time));
}
}
Note: This solves the question, but it operates under the assumption that primes will generate the largest number.