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² 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());
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    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)
            {
                answer = i;
                break;
            }
        }
        return String.valueOf(answer);
    }
    public ArrayList<Integer> Factor (int num)
    {
        ArrayList<Integer> F = new ArrayList<Integer>();
        //F.add(1);
        for (int n = 2; n <= Math.ceil(Math.sqrt(num)); n++)
            if (num % n == 0 && F.contains(n) == false)
            {
                F.add(n);
                if (F.contains(num/n) == false)
                    F.add(num/n);
            }
        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])
                P.add(i);
        return P;
    }
    public ArrayList<Integer> makeOnlyPrime (ArrayList<Integer> F, int i)
    {
        ArrayList<Integer> N = new ArrayList<Integer>();
        for (int f = 0; f <= F.size()-1; f++)
            if (Prime ((int)(i/2)+1).contains(F.get(f)))
                N.add(F.get(f));
        return N;
    }
}