# Euler Problem 47

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

14 = 2 7
15 = 3 5

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

644 = 2&sup2; 7 23
645 = 3 5 43
646 = 2 17 19.

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

I liked this one because it uses two very important routines developed so far. Prime Number generation and Number Factorization. The trick for this one is after factoring a number, filter the set for Prime numbers BEFORE counting the residual factors.

This routine is also getting more complex. In the interest of speeding up the calculation, I moved the Prime ArrayList definition outside of the method so that its a class variable now. This way its only defined once, rather than hundreds of thousands of times.

import java.util.*;

public class Euler47
{
ArrayList<Integer> P = new ArrayList<Integer>();
public static void main(String[] args)
{
Euler47 e = new Euler47();
System.out.format(“Problem: %s\n”, e.getClass().getName());
}
public String Problem ()
{
ArrayList<Integer> F = new ArrayList<Integer>();
int start = 130000, limit = 140000;
int answer = 0, flag = 0, count = 4;
for (int i = start; i < limit; i++)
{
flag = 0;
for (int n = 0; n <= count-1; n++)
{
F = makeOnlyPrime(Factor(i+n), i+n);
if (F.size() == count)
flag++;
}
if (flag == count)
{
break;
}
}
}
public ArrayList<Integer> Factor (int num)
{
ArrayList<Integer> F = new ArrayList<Integer>();
for (int n = 2; n <= Math.ceil(Math.sqrt(num)); n++)
if (num % n == 0 && F.contains(n) == false)
{
if (F.contains(num/n) == false)
}
return F;
}
public ArrayList<Integer> Prime (int lim)
{
P.clear();
boolean [] isPrime = new boolean [lim+1];
for (int i = 2; i < lim; i++)
isPrime[i] = true;
for (int p = 2; p*p < lim; p++)
if (isPrime[p] == true)
for (int m = p*p; m < lim; m = m+p)
if (m % p == 0)
isPrime[m] = false;
for (int i = 2; i < lim; i++)
if (isPrime[i])