Avoid complexities when possible

by Gilbert Keith

Problem 47 involves prime factorizing numbers again;

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?

Since I’d recently learned about Pollard’s rho and how useful it was in prime factorizing, I started off applying it to this problem. the approach is fine, until you hit squares of prime numbers for small primes (9,25, etc.) I seemed to get stuck in an endless loop.

Thinking that I had to have an error in my code, I started looking around for different implementations of the algorithm (not that they’d be super different from what I started out with anyway) but I just wanted to confirm my original track.

Then I saw the second post on this random forum (link):

In fact, one can detect prime powers in practically linear time. It’s also generally a good idea to do trial division by the first few primes before pulling out stronger factorization algorithms.

This totally made sense in my case.

I then wrote the code from scratch (in ~25 to 30 minutes, a new record!) and got the answer fairly easily. The algorithm is pretty simple.

Ingredients: a pre-generated list of primes.

Method: for each number, cache it in a temp value at the beginning of the method. check if it belongs to the list of primes. If it doesn’t, then  go through the list of primes and do a trial division. If the modulus is 0, then divide the cached value by the prime and if the prime isn’t already in the list of prime factors for that number, then add it to the list. Repeat until you whittle down the cached value to a prime number.

This runs in about 125 ms. (when I did it the first time around it ran in about 1100, but I realized that I could move one of the if blocks in the primeFactorSimple method to save me about 1 whole second.

import java.util.ArrayList;
import java.util.Arrays;

public class Problem47 {

	/**
	 * @param args
	 */
	static long start = System.currentTimeMillis();
	static boolean[] boolArr = PrimeGen.generatePrimeArray(1000000);
	static int[] primeArr = PrimeGen.generateCompactPrimeArray(boolArr);
	static long end;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub	
		long N = 2L;
		boolean done = false;
		int numberDistinctPrimes = 4;
		long[] lastValuesCached = new long[numberDistinctPrimes+1];
		int counter = 0;
		while ((!done)) {
			//System.out.println("N: " + N);
			ArrayList <Long> listArr = simpleMethod(N);
			if (!(listArr.size() == numberDistinctPrimes)) {
				Arrays.fill(lastValuesCached, 0);
				counter = 0;
			}
			else {
				counter++;
				lastValuesCached[counter]=N;
				lastValuesCached[0]=counter;
			}
			if (lastValuesCached[0]==numberDistinctPrimes) {
				done = true;
			}
        N++;  
        }
		System.out.println("Answer: " + lastValuesCached[1]);
		end = System.currentTimeMillis();
		System.out.println("Time: " + (end-start) + " ms");
	}
	
	public static ArrayList<Long> simpleMethod(long N) {
		ArrayList<Long> arr = new ArrayList<Long>();
		primeFactorSimple(N,arr);
		return arr;
	}
	
	public static void primeFactorSimple (long N, ArrayList<Long> list) {
		if (N > 1000000) return;	
		long tempN = N;
		
		do {
			int i = 0;
			if (boolArr[(int) tempN]) {
				list.add(N);
				return;
			}
			boolean tempNChanged = false;
			while (!tempNChanged) {
				long prime = (long) primeArr[i];
				if (tempN % prime == 0) {
					tempN = tempN/prime;
					tempNChanged=true;
					if (list.contains(prime)) continue;
					list.add(prime);
				}
				i++;
			}
		} while(tempN!=1);
	}
}

Advertisements