Problem 047


Project Euler

Distinct primes factors

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 prime factors. What is the first of these numbers?


This problem is working with prime and prime factorization again and we should have a prime sieve working by now. The real decision was whether to remember the number of distinct prime factor for each composite number while we are creating our list of prime. Since each time we find a new prime, we visit all the number that is multiple of that prime and cross them off, we are essentially visiting the number each time we find a distinct prime for it. Therefore, we can increment a counter for each number to record this fact with any prime number have 0 count. The only problem with this approach is to set an upper limit for the number we will visit. I choose a million again and the answer is well below the limit.

 

Advertisements