## 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

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)) {
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);
}