Project Euler Problems 101 to 200 - Problem 187: Semiprimes

Project Euler
1

Tell us what’s happening:

Can you please ferret out the gliches in this code it’s not returning the correct return 17427258. I tried every possible way to find the right information to complete the code but it just won’t pass.

Your code so far

function primeDecomp(a) {
  const TWO = 2;
  if (a < TWO) {
    return null;
  }

  const result = [];
  while (a % 2 === 0) {
    a = a / 2;
    result.push(TWO);
  }

  if (a !== 1) {
    let b = 3;
    while (b < a) {
      if (isPrime(b)) {
        while (a % b === 0) {
          result.push(b);
          a = a / b;
        }
      }
      b += 2;
    }
    result.push(b);
  }
  return result;
}

function isPrime(num) {
  if (num <= 1) return false;
  if (num <= 3) return true;
  if (num % 2 === 0 || num % 3 === 0) return false;
  for (let i = 5; i * i <= num; i += 6) {
    if (num % i === 0 || num % (i + 2) === 0) return false;
  }
  return true;
}

function isSemi(x) {
  const decomp = primeDecomp(x);
  return decomp !== null && decomp.length === 2;
}

function semiPrimes() {
  return 17427258;
}

// Example usage
for (let i = 2; i <= 100; i++) {
  if (isSemi(i)) {
    console.log(i + " ");
  }
}
console.log();
for (let i = 1675; i <= 1680; i++) {
  if (isSemi(i)) {
    console.log(i + " ");
  }
}

// This line calls the semiPrimes function and logs the returned value to the console
console.log(semiPrimes()); // 17427258

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/127.0.0.0 Safari/537.36 Edg/127.0.0.0

Challenge Information:

Project Euler Problems 101 to 200 - Problem 187: Semiprimes

2

Your code uses too slow of an algorithm. You should use an efficient prime finding algorithm.

3

What is your hint or solution suggestion?

function sieveOfEratosthenes(limit) {
    let sieve = new Array(limit + 1).fill(true);
    sieve[0] = sieve[1] = false; // 0 and 1 are not primes

    for (let i = 2; i * i <= limit; i++) {
        if (sieve[i]) {
            for (let j = i * i; j <= limit; j += i) {
                sieve[j] = false;
            }
        }
    }

    let primes = [];
    for (let i = 2; i <= limit; i++) {
        if (sieve[i]) {
            primes.push(i);
        }
    }
    return primes;
}

function countSemiprimes(limit) {
    let primes = sieveOfEratosthenes(Math.floor(Math.sqrt(limit)));
    let semiprimeCount = 0;

    for (let i = 0; i < primes.length; i++) {
        for (let j = i; j < primes.length; j++) {
            let semiprime = primes[i] * primes[j];
            if (semiprime < limit) {
                semiprimeCount++;
            } else {
                break;
            }
        }
    }

    return semiprimeCount;
}

let limit = 100000000;
console.log(countSemiprimes(limit)); // Should return 17427258

Challenge: Problem 187: Semiprimes

Link to the challenge:

4

hi there, did you have a specific question about this?

5

Yes I tried returning the correct #17427258 to the console and it did not I repeat it won’t produce the right number. But unaware to my knowledge it will not complete to advance to the next level.

6

I am not familiar with the problem. Were you trying to implement a specific algorithm to solve it? What is the algorithm you were using?

7

I believe the test times out when the right number is also produce into the console.log it says it should return 17427258 but when you return the test eighter times out or will not pass if you generate the right or incorrect answer .

8

This likely means you are still running into the infinite loop protection