Project Euler – Problem 47

Problem 47: Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 x 7
15 = 3  5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2^2 x 7 x 23
645 = 3 x 5 x 43
646 = 2 x 17 x 19.

import java.util.Vector;


class runner
{
	public static int numOfDistinctFactors(int n){
		double limit = n/2;
		int c = 0;

		int pp = primes.lastElement();
		while(primes.lastElement() < limit){
			isPrime(++pp);//Check and store primes until limit
		}

		for(int p : primes){
			if(p > limit || n == 1) break;
			if(n % p == 0){
				do{
					n /= p;
				}while(n % p == 0);
				c++;
			}
		}

		return c;
	}

	public static boolean isPrime(int n){
		if(primes.contains(n)) return true;
		double limit = Math.sqrt(n);
		for(int p: primes){
			if(p > limit) break;
			if(n % p == 0) return false;
		}
		primes.add(n);
		return true;
	}

	static Vector primes = new Vector();
	public static void main (String[] args) throws java.lang.Exception
	{
		long time = System.currentTimeMillis();
		primes.add(2);

		int i=644;
		int consec_reset = 4, consec = consec_reset;
		while(true){
			if(numOfDistinctFactors(i) == consec_reset){
				consec -= 1;
			}else{
				consec = consec_reset;
			}

			if(consec == 0) break;
			i++;
		}
		i-=consec_reset-1;
		
		System.out.println("i:"+i);
		System.out.println("time: "+(System.currentTimeMillis() - time));
	}
}


Note: Execution time is about 9.7seconds