Hermann Döppes
2015-12-09 03:16:20
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++;
}
}
热门帖子
热门github
6
Why not products of two primes?
@PatrickCollins Then it will have four divisors instead of three: 1, two primes, and the product itself.
@KenHung Ah, I wasn't thinking of the product itself. Thanks!
The "highly inefficient" comment on the primality test is somewhat of an understatement! But given that you have provided an excellent algorithmic solution and explicitly mentioned using a Sieve, +1