Better solution for finding numbers with exactly 3 divisors

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 1

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

Answer 2

You could implement an algorithm based on the sieve of Eratosthenes. The only change is that you don't mark the multiples of found primes, but the multiples of found numbers which have at least 3 divisors. The reason is that you can be sure that the multiples of these numbers have more than 3 divisors.

EDIT: Hermann's solution is the best for "threesomes". My idea is more general and applicable for "N-somes".