Наибольшая функция простого множителя работает слишком медленно - PullRequest
Новая
       5

Наибольшая функция простого множителя работает слишком медленно

0 голосов
/ 09 сентября 2018

Я написал функцию, которая находит наибольшее простое число некоторого числа. Эта функция работает, но проблема в том, что она слишком медленная. например, когда я ввожу 600851475143 в качестве параметра, процесс нахождения наибольшего простого множителя длится слишком долго. Как я могу изменить его так, чтобы он работал быстрее? Вот мой код: 

class test {

static addArray(someArray, member) {
    for (var i = 0; i <= someArray.length; i++) {
        if (i == someArray.length) {
            someArray[i] = member;
            return someArray;
        }
    }
}
static someLength(someArray) {
    var i = 0;
    while (someArray[i] !== undefined) {
        var lastItem = i;
        i++;
    }
    return i;
}
static testPrime(i) {
    for (var k=2; k < i; k++) {
        if (i % k == 0) {
            return false;
        }       
    }
    return true;
}
}

var primeArray = [];
function largestPrime(n) {
    for (var i=2; i < n; i++) {
        //var k = n / i;
        if (n % i == 0 && test.testPrime(i) == true) {  
            test.addArray(primeArray, i);
            n == n / i;
        }
    }
    return primeArray[test.someLength(primeArray) - 1];
}

document.write(largestPrime(600851475143));

1 Ответ

0 голосов
/ 09 сентября 2018

Хорошо, прежде чем мы углубимся в это, давайте рассмотрим немного теории. То, как вы измеряете время, необходимое для выполнения определенного фрагмента кода, математически обозначается через нотацию O(n) (нотация big-o), где n - это размер ввода.

Ваша тестовая функция простого числа имеет нечто, называемое linear complexity, что означает, что она станет линейно медленной, когда размер n (в данном случае ввод вашего числа) станет большим.

Для числа 15 контекст выполнения выглядит следующим образом: 

15 % 2 == 0 (FALSE)
15 % 3 == 0 (TRUE)
...
15 % 14 == 0 (FALSE)

Это означает, что для числа 100 будет 98 (2 - 99) шагов. И это будет расти со временем. Давайте учтем ваш номер: 600851475143. Программа выполнит 600851475143; for-loop будет срабатывать 600,851,475,141 раз.

Теперь давайте рассмотрим тактовый цикл. Скажем, каждая инструкция занимает 1 clock cycle, а тупая версия вашего цикла занимает 2, число 600851475143 будет выполнено 1,201,702,950,286 раз. Учтите, что каждый тактовый цикл занимает 0.0000000625 секунды (для 16-МГц платформы, такой как Arduino ), время, затрачиваемое только на этот код: 

0.0000000625 * 1201702950286 = ~75,106 seconds

или около 20 hours.

Вы видите, куда я иду с этим.

Лучше всего, чтобы эта программа работала быстрее - использовать вероятностный тест и подтвердить свои результаты, используя этот номер (или его вариант BigInteger).

Ваш подход является более линейным, в том смысле, что число итераций для for-loop для проверки простоты увеличивается с увеличением числа. Вы можете отобразить время цикла процессора вместе с числом, и вы поймете, что это довольно неэффективный способ сделать это.

У меня есть дискретная математика в моем Uni, так что просто слово предупреждения - тесты на первичность и их варианты становятся действительно грязными, когда вы попадаете в утопию более быстрых и более быстрых тестов. Это путь, заполненный шипами математики, и вы должны иметь ремень безопасности при езде по джунглям! ;)

Если вам нужна дополнительная информация по этому вопросу, я был бы рад помочь! Я надеюсь, что это помогло! :)

...