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?


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)) {
   base = dpf.get(number);
   if(base.size() != 4) {
      dpf.remove(number); //remove existing number from map
      number += 1;
   if(!dpf.containsKey(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
   if(!dpf.containsKey(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
   if(!dpf.containsKey(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

   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 {
      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?


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.