Лучшее решение для нахождения чисел с ровно 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

Единственные числа втроем - это квадраты простых чисел (делители 1, p, p ^ 2). Просто сделайте Erathostenes и верните квадраты.

Доказательство. Если оно имеет нечетное число делителей, то оно известно как квадрат. Так как 1 и n ^ 2 всегда являются дивизорами n ^ 2, мы можем иметь только один дивизор, т.е. N. Любой делитель 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++;
  }
}

Ответ 2

Вы можете реализовать алгоритм, основанный на сите Eratosthenes. Единственное изменение заключается в том, что вы не отмечаете кратность найденных простых чисел, а кратность найденных чисел, которые содержат не менее 3 делителей. Причина в том, что вы можете быть уверены, что кратные числа этих чисел имеют более 3 делителей.

РЕДАКТИРОВАНИЕ: решение Германа является лучшим для "тройки". Моя идея более общая и применима для "N-somes".

Ответ 3

Более оптимизированным решением является поиск первых N простых чисел и их квадратов. Идея заключается в том, что простые числа делятся только двумя числами. Таким образом, числа, делящиеся только на три числа, имеют дополнительный делитель, который должен быть его квадратным корнем. Он должен быть простым, поэтому он не добавляет дополнительный разделитель к основным разделителям чисел.

function threesomeNumber(N){
    return firstPrimes(N).map(function(x){return x*x})
}

Где firstPrimes - это функция, которая возвращает первые N простые числа.

Ответ 4

Здесь простой:

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

            // Stop trying if more that 3 Divisions are Found
            if(numberOfDivisions > 3)
               break;
        }

        if(numberOfDivisions === 3)
        {
            found++;
            console.log(found + " = " + i);
        }

        numberOfDivisions = 1;
        i++;
    }
}