Project Euler: Problem 47 – Distinct primes factors

Problem 47:

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?

Idea:

This seemed like a pretty simple problem, until the second example included a prime factor to a power. My first task is to get the distinct prime factors, including prime factors to a power. I already had a method that would return a list of the prime factors, so I just called that method, sorted the list, and combined like terms to get a list of distinct prime factors, including those raised to a power.
 
The next order of business is to start finding the numbers for the solution. I started with 210 (smallest number with 4 distinct prime factors), even though I was pretty certain the answer would be larger than 646 in the example, however I didn’t want to make any false assumptions.
 
I started with 210 as the “base” number and incremented by 1 until I found a base number with exactly 4 distinct prime factors, and stored that number, and the list of factors, in a map. Then I added 1 to the base number, and checked that to see if it had 4 distinct prime factors. I repeated this until I got to the “base+3” that had 4 distinct prime factors, storing all the numbers and their respective list of distinct prime factors in a map. If any numbers in between didn’t have exactly 4 distinct prime factors, I discarded all the numbers I had saved so far, and incremented my base number by that amount.
 
When I found a “base+3” with 4 distinct prime factors, I checked to see if the 4 lists of prime factors were all mutually disjoint. If they were, the “base” number was the answer; if they weren’t, I incremented the base number by 1 and continued my search. I chose to only increment by 1 instead of 3-4 in case I ran into a situation where, for example, there were 4 or more consecutive numbers who had exactly 4 distinct prime factors, and it just so happens that the first number in the series shares factors with one of the next 3 numbers, but the second number in the series is the start of the 4 numbers that all have mutually distinct prime factors.
 
During execution, I used the debugger in Eclipse and recognized most of the program execution time was in finding the prime factors. I left a note to myself that the program could be more efficient if I used a sieve method for finding the factors, but I got the program working, and as a rule that was drilled into me from school: make it work first, optimize later.

//IMPROVE: use sieve approach to count # of factors
//and don't save all the factors to compare
int answer = -1;

boolean done = false;
int number = 210; //2*3*5*7 (smallest number w/ 4 distinct prime factors)
List<Integer> base,plus1,plus2,plus3;
Map<Integer ,List<Integer>> dpf = new Hashtable<Integer ,List<Integer>>();
while(!done) {
   if(!dpf.containsKey(number)) {
      dpf.put(number,EulerUtils.distinctPrimeFactors(number));
   }
   base = dpf.get(number);
   if(base.size() != 4) {
      dpf.remove(number); //remove existing number from map
      number += 1;
      continue;
   }
  
   if(!dpf.containsKey(number+1)) {
      dpf.put(number+1,EulerUtils.distinctPrimeFactors(number+1));
   }
   plus1 = dpf.get(number+1);
   if(plus1.size() != 4) {
      dpf.remove(number); //remove base number from map
      dpf.remove(number+1); //remove plus1 number from map
      number = (number+1)+1; //skip ahead to plus2 number
      continue;
   }
  
   if(!dpf.containsKey(number+2)) {
      dpf.put(number+2,EulerUtils.distinctPrimeFactors(number+2));
   }
   plus2 = dpf.get(number+2);
   if(plus2.size() != 4) {
      dpf.remove(number); //remove base number from map
      dpf.remove(number+1); //remove plus1 number from map
      dpf.remove(number+2); //remove plus2 number from map
      number = (number+2)+1; //skip ahead to plus3 number
      continue;
   }
  
   if(!dpf.containsKey(number+3)) {
      dpf.put(number+3,EulerUtils.distinctPrimeFactors(number+3));
   }
   plus3 = dpf.get(number+3);
   if(plus3.size() != 4) {
      dpf.remove(number); //remove base number from map
      dpf.remove(number+1); //remove plus1 number from map
      dpf.remove(number+2); //remove plus2 number from map
      dpf.remove(number+3); //remove plus3 number from map
      number = (number+3)+1; //skip ahead to the 5th number
      continue;
   }

   if(Collections.disjoint(base, plus1) && Collections.disjoint(base, plus2) &&
         Collections.disjoint(base, plus3) && Collections.disjoint(plus1, plus2) &&
         Collections.disjoint(plus1, plus3) && Collections.disjoint(plus2, plus3)) {
      answer = number;
      done = true;
   } else {
      dpf.remove(number);
      number += 1;
   }
}

Project Euler: Problem 12 – Highly divisible triangular number

Problem 12:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
 
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
 
Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.
 
What is the value of the first triangle number to have over five hundred divisors?

Idea:

Since we don’t need the actual divisors, only the number of divisors, I wrote a separate method that does just that by looping from 1 to the square root of the supplied number, and checking to see if those numbers divide evenly into the supplied number, and if so, incrementing a counter.
 
From there, just generate the triangle numbers as you go and feed them into the method until you find a number that has more than 500 divisors.

long answer = -1;

long number = 0;
long count = 0;
long divisors = 0;

while(divisors < 500) {
   count += 1;
   number += count; //1+2+...+n
   divisors = getNumberDivisors(number);
}

answer = number;

System.out.println("Answer: "+answer);

Note: “getNumberDivisors(long)” is a helper method I wrote that gets the number of divisors of the given long.