Better solution for finding numbers with exactly 3 divisors

The only threesome numbers are squares of primes (divisors 1, p, p^2). Just do Erathostenes and return the squares.

Proof: If it has an odd number of divisors it is known to be a square. Since 1 and n^2 are always divisors of n^2, we may only have one more divisor, i.e. n. Any divisor of n would be another divisor of n^2, therefore n is prime.

Example (based on given code):

function threesomeNumber(N) {
var found = 0;
var i = 2;
var prime = true;
while (found < N) {
    // Naive prime test, highly inefficient
    for (var j = 2; j*j <= i; j++) {
        if (i % j === 0) {
            prime = false;
        }
    }
    if (prime) {
        found++;
        console.log(found + " = " + (i*i));
    }
    prime = true;
    i++;
  }
}

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)