Project Euler 187

Programming JavaScript
1

What is your hint or solution suggestion?

Challenge: Problem 187: Semiprimes

Link to the challenge:

This is my code, but I can’t get the requested result to return. Can someone help me?

function semiPrimes(limit) {
    let sieve = [];
    let primes = [2];

    function isPrime(x) {
        if ((x & 1) === 0) {
            return x === 2;
        }
        return sieve[x >> 1];
    }

    function fillSieve(size) {
        const half = size >> 1;
        sieve = new Array(half).fill(true);
        sieve[0] = false;

        const sqrtSize = Math.sqrt(size);
        for (let i = 1; i < (sqrtSize >> 1); i++) {
            if (sieve[i]) {
                for (let current = 3 * i + 1; current < half; current += 2 * i + 1) {
                    sieve[current] = false;
                }
            }
        }
    }

    let largestPrime = Math.floor(limit / 2) + 100;
    fillSieve(largestPrime);

    for (let i = 3; i < largestPrime; i += 2) {
        if (isPrime(i)) {
            primes.push(i);
        }
    }

    let count = 0;
    for (let i = 0; i < primes.length && primes[i] * primes[i] < limit; i++) {
        for (let j = i; j < primes.length && primes[i] * primes[j] < limit; j++) {
            count++;
        }
    }

    return count;
}

const limit = 100000000;
console.log(semiPrimes(limit));
2

I’d really, really, really recommend you avoid bitwise operations like this.

5

I tried to follow your advice, but it gives me a timeout.

6

What does your code look like without any of those bitwise operations?

7

This is what the code looks like after your suggestion.

function semiPrimes(limit) {
    let sieve = [];
    let primes = [2];

    function isPrime(x) {
        for (let i = 3; i * i <= x; i += 2) {
            if (x % i === 0) {
                return false;
            }
        }
        return true;
    }

    function fillSieve(size) {
        const half = size >> 1;
        sieve = new Array(half).fill(true);
        sieve[0] = false;

        const sqrtSize = Math.sqrt(size);
        for (let i = 1; i < Math.floor(sqrtSize / 2); i++) {
            if (sieve[i]) {
                const current = 3 * i + 1;
                for (let j = current * current; j < size; j += 2 * current) {
                    sieve[Math.floor(j / 2)] = false;
                }
            }
        }
    }

    let largestPrime = Math.floor(limit / 2) + 100;
    fillSieve(largestPrime);

    for (let i = 3; i < largestPrime; i += 2) {
        if (isPrime(i)) {
            primes.push(i);
        }
    }

    let count = 0;
    for (let i = 0; i < primes.length && primes[i] * primes[i] < limit; i++) {
        for (let j = i; j < primes.length && primes[i] * primes[j] < limit; j++) {
            count++;
        }
    }

    return count;
}

const limit = 100000000;
console.log(semiPrimes(limit));
8

You still need to use the seive

9

Sorry for my English, but I honestly didn’t understand what I should do on that string. Could you be more precise?

10

What string?

Here you are doing weird bit shifting. You should do this exact same logic, but without the bit shifting

This code isn’t doing the same thing