Project Euler Solution #47: 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 each. What is the first of these numbers?

Solution

The easiest way to find the first 4 consecutive numbers that have 4 unique prime factors is probably to use brute force from 2 to infinity. Once we have found a number that has 4 unique prime factors, we increment a counter and test the next one until we find a sequence of length 4 in this way. The only improvement would be to start with 2 × 3 × 5 × 7 = 210 rather than 2, as this is the smallest possible solution.

However, a better variant is to modify the Sieve of Eratosthenes, similar to what we have done in Problem 72, in the sense that we store the number of unique factors instead of a boolean:

const horizon = 20000;
const primCount = new Uint8Array(horizon + 1);
for (let i = 2; i <= horizon; i++) {
    if (primCount[i] === 0) {
        for (let j = i; j <= horizon; j+= i) {
            primCount[j]++;
        }
    }
}

All you have to do now is test if 4 consecutive numbers in the array have the entry 4:

let count = 0;
for (let i = 2 * 3 * 5 * 7; i <= horizon; i++) {

    if (primCount[i] === 4) {
        count++;
        if (count === 4) {
            console.log(i - 3);
            break;
        }
    } else count = 0;
}

Since the two steps can be handled independently, we can easily combine both outer loops for the final solution:

function solution(horizon, numFactors, seqLength) {

    let count = 0;
    const primCount = new Uint8Array(horizon + 1);
    for (let i = 2; i <= horizon; i++) {

        if (primCount[i] === numFactors) {
            count++;
            if (count === seqLength) {
                return i - seqLength + 1;
            }
        } else {
            count = 0;
            if (0 === primCount[i]) {
                for (var j = i; j <= horizon; j+= i) {
                    primCount[j]++;
                }
            }
        }
    }
    return null;
}
solution(150000, 4, 4);