Krzysztof Kraszewski Krzysztof Kraszewski - 2 months ago 11
Javascript Question

Better solution for finding numbers with exactly 3 divisors

I was studying some programming and I found an exercise to write an algorithm finding "threesome numbers" (numbers that are divisible by exactly 3 numbers). I wrote this:

function threesomeNumber(N) {
var found = 0;
var i = 1;
var numberOfDivisions = 1;
while (found < N) {
for (var j = 2; j <= i; j++) {
if (i % j === 0) {
numberOfDivisions++;
}
}
if (numberOfDivisions === 3) {
found++;
console.log(found + " = " + i);
}
numberOfDivisions = 1;
i++;
}
}


The problem is it's running kinda slow and I was wondering if it can be done quicker. Does anybody know of a more optimized solution? I want it to find N consecutive threesome numbers.

Answer

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++;
  }
}