Анализ различных методов поиска простого числа в Python

Если вы участвуете в соревновательном программировании, вы, возможно, знакомы с тем фактом, что вопросы, связанные с простыми числами, являются одним из вариантов, который может выбрать тот, кто ставит задачи. Здесь мы обсудим, как оптимизировать вашу функцию, которая проверяет простое число в заданном наборе диапазонов, а также рассчитает время их выполнения.

По определению, простое число - это целое положительное число, которое делится только на себя и 1. Например: 2,3,5,7. Но если число можно разложить на меньшие числа, оно называется составным числом. Например: 4 = 2 * 2, 6 = 2 * 3

И целое число 1 не является ни простым, ни составным числом. Проверить, что число является простым, легко, но для эффективной проверки требуются некоторые усилия.

Способ 1:

Давайте теперь перейдем к самой первой функции, чтобы проверить, является ли число, скажем n, простым или нет. В этом методе мы проверим все делители от 2 до n-1. Мы пропустим 1 и n. Если n делится на любой из делителей, функция вернет False, иначе True.

Ниже приведены шаги, используемые в этом методе:

1. Если целое число меньше 1, возвращается False.
2. Если данное число делится на любое из чисел от 2 до n, функция вернет False.
3. В противном случае он вернет True

Python3

Выход:

В приведенном выше коде мы проверяем все числа от 1 до 100000, являются ли эти числа простыми или нет. Как показано, у него огромная среда выполнения. Бег занимает около 1 минуты. Это простой подход, но для его выполнения требуется много времени. Таким образом, это не является предпочтительным в соревновательном программировании.

Способ 2:

В этом методе мы используем простой трюк, уменьшая количество проверяемых делителей. Мы обнаружили, что есть тонкая линия, которая действует как зеркало, поскольку показывает факторизацию под линией и факторизацию над линией в обратном порядке. Линия, разделяющая множители на две половины, является линией квадратного корня из числа. Если число является точным квадратом, мы можем сдвинуть строку на 1 и получить целочисленное значение линии, которая делится.

1. Если целое число меньше 1, возвращается False.
2. Теперь мы уменьшаем числа, которые необходимо проверить, до квадратного корня из заданного числа.
3. Если данное число делится на любое из чисел от 2 до квадратного корня из числа, функция вернет False.
4. В противном случае он вернет True

Python3

Выход:

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

Способ 3:

1. Если целое число меньше 1, возвращается False.
2. Если число равно 2, он вернет True.
3. Если число больше 2 и делится на 2, оно вернет False.
4. Теперь мы проверили все четные числа. Теперь поищите нечетные числа.
5. Если данное число делится на любое из чисел от 3 до квадратного корня из числа, пропуская все четные числа, функция вернет False
6. В противном случае он вернет True

Python3

Выход:

В приведенном выше коде мы проверяем все числа от 1 до 100000, являются ли эти числа простыми или нет. На выполнение программы уходит сравнительно меньше времени, чем на все предыдущие методы. Это наиболее эффективный и быстрый способ проверить простое число. Поэтому он наиболее предпочтителен в соревновательном программировании. В следующий раз при попытке задать какой-либо вопрос в соревновательном программировании используйте этот метод для достижения наилучших результатов.

Метод сита:

Этот метод печатает все простые числа, меньшие или равные заданному числу n. Например, если n равно 10, на выходе должно быть «2, 3, 5, 7». Если n равно 20, на выходе должно быть «2, 3, 5, 7, 11, 13, 17, 19».

Этот метод считается наиболее эффективным для генерации всех простых чисел, меньших заданного числа n. Считается, что это самый быстрый способ создания списка простых чисел. Этот метод не подходит для проверки конкретного числа. Этот метод предпочтительнее для создания списка всех простых чисел.