Project Euler

Problem 47: Distinct Primes Factors

The first two consecutive numbers to have two distinct prime factors are:
14 = 2 x 7
15 = 3 x 5
The first three consecutive numbers to have three distinct prime factors are:
644 = 2² x 7 x 23
645 = 3 x 5 x 43
646 = 2 x 17 x 19.
Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?

The Catch

How to find the number of distinct prime factors.

The Light

We could use the prime factorization method discussed in Problem 3 to find a number's prime factors and count repeated prime factors once only. This algorithm is, however, not as efficient when dealing with large number.

Prime factorize 812:
812 / 2 = 406
406 / 2 = 203
203 % 2 != 0 (skip 2)
203 % 3 != 0 (skip 3)
203 / 7 = 29
29 % 11 != 0 (skip 11)
29 % 13 != 0 (skip 13)
29 % 17 != 0 (skip 17)
29 % 19 != 0 (skip 19)
29 % 23 != 0 (skip 23)
29 / 29 = 1

There is a series of primes numbers that are being checked unnecessarily after 7. For even larger numbers, this series of skipped primes will greatly slow down the execution time.

It is important to notice that after 7, there is only 1 prime factor left. Also notice that this last prime factor is greater than sqrt(812) = 28.4956. This is due to the fact that for any given integer n, there is only 1 prime factor that is greater than √n. Use this fact to eliminate all unnecessary checks.

To prime factorize, you will need a list of precalculated prime numbers, which can be achieved using the Sieve of Eratosthenes as discussed in Problem 35.

The Code

import java.util.*;

public class Problem47
{
  static List prime = generatePrimes(100000);

  public static void main(String[] args)
  {
    int count = 0;
	int result = 0;

	for(int i = 647; count != 4; i++)
	{
	  if(numOfDistinctPrimeFactors(i) == 4)
	  {
	    count++;
	    result = i;
	  }
	  else
	    count = 0;
	}
	System.out.println(result - 3);
  }
  
  public static int numOfDistinctPrimeFactors(int n)
  {
    int distinct = 0;
	for(int i = 0;; i++)
	{
      if ((int)prime.get(i) * (int)prime.get(i) > n)
		return ++distinct;
     
	  if(n % (int)prime.get(i) == 0)
	    distinct++;
	  else
	    continue;
		
	  while(n % (int)prime.get(i) == 0 && n > 1)
	  {
	    System.out.println(prime.get(i));
	    n /= (int)prime.get(i);
	  }
	  if(n == 1)
	    break;
	}
	return distinct;
  }
  
  public static List generatePrimes(int max) 
  {
    boolean[] isComposite = new boolean[max + 1];
    for (int i = 2; i * i <= max; i++) 
    {
      if (!isComposite [i]) 
        for (int j = i; i * j <= max; j++) 
        {
          isComposite [i*j] = true;
        }
    }   
    ArrayList list = new ArrayList();
 
    for (int i = 2; i <= max; i++)  
    {
      if (!isComposite [i]) 
        list.add(new Integer(i));
    }
    return list;
  }
}