找到具有正好3个除数的数字的更好解决方案

我正在研究一些编程,我找到了一个练习来编写一个算法,找到"三个数字"(数字可以被3个数字整除).我写了这个:

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

问题是它运行有点慢,我想知道它是否可以更快地完成.有人知道更优化的解决方案吗？我希望它能找到N个连续的三人组号码.

唯一的三个数字是素数的平方(除数1,p,p ^ 2).只做Erathostenes并返回正方形.

证明:如果它具有奇数个除数,则称其为正方形.由于1和n ^ 2总是n ^ 2的除数,我们可能只有一个除数,ien n的除数将是n ^ 2的另一个除数,因此n是素数.

示例(基于给定代码):

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

你可以实现一个基于Eratosthenes筛的算法.唯一的变化是你没有标记找到的素数的倍数,但是找到的数字的倍数至少有3个除数.原因是你可以确定这些数字的倍数有超过3个除数.

编辑:赫尔曼的解决方案是最好的"三人行".我的想法更为通用,适用于"N-somes".