Если вы потратили какое-то время на войны кодов, определение того, является ли число простым, является общей темой среди категорий проблем. Когда я впервые начал кодировать, я подумал, что перебрать все числа от 1 до num и проверить, делится ли оно, было отличным подходом. Однако, как только я узнал о большой нотации O, я был огорчен!
После некоторого исследования и чтения wiki в эти выходные я нашел отличную функцию для определения того, является ли число простым с сублинейным временем O (n). Я нашел следующее решение:
function isPrime (num) { if (num <= 1) { return true } else if (num <= 3) { return true } else if (num%2 === 0 || num%3 === 0) { return false } let i = 5 while (i*i <= num) { if (num%i === 0 || num%(i+2) === 0) { return false } i += 6 } return true }
Подход
- Проверяет, является ли число 0, 1 или отрицательным. Возвращает
true
, если число находится в этом диапазоне. - Проверяет, равно ли число 2 или 3. Возвращает
true
, если число равно 2 или 3. - Последний оператор
if
возвращает, что число не является простым, если оно делится на 2 или 3. - Последняя часть этой функции самая сложная - цикл while! По сути, он проверяет каждое нечетное число, которое не делится на 3, пока оно не станет больше квадратного корня из числа. Например, первые
i
иi + 2
будут 5 и 7. Следующиеi
иi + 2
будут 11 и 13. Он не проверяет 9 или 15, потому что оба делятся на 3 и попали бы в последнийelse if
заявление. - Наконец, возвращает
true
, если число не делилось ни на какиеi
илиi+2
записи, потому что число простое.
O(n)
Если мы предположим, что n - это число, переданное в isPrime, O (n) моего первоначального [не так хорошо] подхода будет O (n). Следовательно, эта временная сложность будет линейной. Это нормально, если все, что вы делаете, - это проверка, но во многих случаях эта функция является вспомогательной, и проверка того, является ли список чисел простым, будет экспоненциальной.
Вышеупомянутая функция isPrime
будет O (n ^ ¹ / 2). Это означает, что временная сложность будет сублинейной, что значительно снизит временную сложность более крупной функции.
В заключение
Есть много способов проверить, является ли число простым. Существуют эвристические программы, которые проверяют вероятность того, что число является простым. Другая стратегия - использование теоретико-числового метода. Если вы нашли какие-либо интересные способы решения этой проблемы, прокомментируйте их ниже или напишите мне по адресу [email protected].