В: Как проверить, является ли данное целое простым простым или нет?
Это был еще один вопрос, который мне задали во время технического собеседования, и в то время я помню, как пытался найти реальное решение, которое также было бы эффективным.
Решение, которое я придумал, имело недостатки с точки зрения эффективности. В то время подход заключался в проведении некоторого первоначального тестирования чисел, равных или меньших 3, и больших или равных -1 в качестве простых чисел.
Следующим шагом я должен был проверить числа от 3 до половины числа. Идея заключалась в том, что был бы меньший множитель, меньший или равный половине, если бы число не было простым.
Я уточнил код из интервью, сохранив первоначальную идею. (Увидеть ниже)
Проблема с этим кодом - время выполнения. Несмотря на то, что это метод грубой силы, временная сложность в этом случае составляет O (n). Это определенно решение, но не эффективное. Например, давайте рассмотрим большое простое число, скажем 179426549, требуется около 6,69 секунды, чтобы проверить, является ли оно простым.
Итак, после собеседования я потратил некоторое время на размышления о том, как повысить эффективность метода грубой силы, и вспомнил тест на простоту для книги Скиены «Руководство по разработке алгоритмов», где говорилось о выполнении поиска по коэффициенту грубой силы до квадратного корня из число.
Это определенно улучшило бы алгоритм, поскольку он не учитывает значительное количество факторов. Он по-прежнему использует ту же идею, что малый множитель меньше квадратного корня из числа, а не половины числа.
Вот код того же.
Обратите внимание, что временная сложность в этом случае составляет O (√n). Например, давайте рассмотрим большое простое число, скажем 179426549, для проверки того, является ли оно простым, требуется около 0,0036 секунды, и это значительно лучше, чем 6,69 секунды. ранее.
Существуют более эффективные методы проверки того, является ли число простым, особенно когда мы проверяем достаточно большие простые числа, используемые в криптографии. Я изучу некоторые другие алгоритмы, такие как Маленькая теорема Ферма и Миллера-Рабина, в следующей части этой серии тестов на простоту.
