Krzysztof Kraszewski - 1 year ago 78

Javascript Question

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 Source

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