Krzysztof Kraszewski - 1 year ago 105
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.

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++;
}
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download