Как понять что число простое в питоне
Алгоритм нахождения простых чисел
Оптимизация алгоритма нахождения простых чисел
Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.
Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.
Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.
Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.
Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.
А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим — это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.
Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.
В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:
Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.
P.S.
Благодаря замечаниям получаем Листинг 7:
при N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053
Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143
Проверьте, является ли число простым в Python
Простое число может быть изображено как натуральное число без других положительных делителей, кроме числа 1 и самого себя. Число 1 не учитывается в списке простых чисел.
В этом руководстве будут рассмотрены различные методы, которые вы можете использовать, чтобы проверить, является ли число простым.
Используйте простой метод итерации для определения простого числа в Python
В следующем коде используется метод простой итерации, чтобы проверить, является ли данное число простым числом в Python.
Вы можете оптимизировать приведенный выше код, применив некоторые изменения. Сделайте следующие оптимизации, чтобы сделать код еще быстрее:
Проверяйте, пока не будет достигнут корень данного числа, вместо проверки точного числа. Этот процесс в основном устраняет избыточность, которая возникает, когда больший множитель числа K кратен меньшему множителю, который уже был повторен.
Все простые числа существуют в форме 6n ± 1, за исключением 2 и 3. Следовательно, проверка делимости данного числа на 2 и 3, а затем проверка каждого числа, имеющего форму 6n ± 1, является более эффективным решением.
В следующем коде используется оптимизированный метод простой итерации, чтобы проверить, является ли данное число простым числом в Python.
Оптимизированный метод итерации делает его быстрее и эффективнее, чем простой метод итерации, примерно на 30%.
Следует отметить, что любое отрицательное число не подпадает под критерии простых чисел. Вывод этих функций может измениться, если ему сопоставить какое-либо отрицательное число.
Python Exercise: проверить число простое или нет
Python Exercises, Practice and Solution: Write a Python function that takes a number as a parameter and check the number is prime or not.
Пример
def is_prime(a): if a 8 ответов
Вот мой взгляд на проблему:
from math import sqrt; from itertools import count, islicedef isPrime(n): return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))
#1 Дек. 23, 2011 22:41:12
Определение простое число или нет
i=2.000
while x>i:
if x%i!=0:
i=i+1
print “prostoe”
else:
print “ne prostoe”
break
логически я понимаю так, перебирал разные варианты, но нужного результата нет(((( В какую сторону копать? Направте плиз! Или хотябы логику скажите, как оно должно работать. Спасибо!
Отредактировано (Дек. 23, 2011 22:58:02)
#2 Дек. 23, 2011 23:33:21
Определение простое число или нет
Описание
Я дам вам некоторые подробности об этой почти эзотерической единственной строке кода, которая проверит простые числа:
xrange(2147483647+1) # OverflowErrorfrom itertools import count, islicecount(1) # Count from 1 to infinity with step=+1islice(count(1), 2147483648) # Count from 1 to 2^31 with step=+1islice(count(1, 3), 2147483648) # Count from 1 to 3*2^31 with step=+3
Давайте найдем все делители n = 100 и перечислим их в таблицу:
2 x 50 = 100 4 x 25 = 100 5 x 20 = 10010 x 10 = 100 #5 Дек. 25, 2011 02:18:08
Определение простое число или нет
Будет работать заметно быстрее, если этот цикл заменить на:
Проверка, является ли число простым числом в Python
Я написал следующий код, который должен проверить, является ли введенный номер простым числом или нет, но есть проблема, с которой я не мог пройти:
Если введенный номер не является простым числом, он отображает «не просто», как и предполагалось, но если число является простым числом, оно ничего не отображает. Не могли бы вы мне помочь?
ОТВЕТЫ
Ответ 1
Существует много эффективных способов проверки примитивности (и это не один из них). Но цикл, который вы написали, может быть кратко представлен в Python:
То есть, a является простым, если все числа между 2 и a (не включительно) дают ненулевой остаток при делении на a.
Ответ 2
На самом деле я не думаю, что в этих ответах найдено наилучшее решение, поэтому я собираюсь опубликовать свое сообщение и объяснить, почему это лучше:
Описание
Я собираюсь дать вам немного информации об этой почти эзотерической одиночной строке кода, которая будет проверять простые числа:
Найдем все делители n = 100 и перечислим их в таблице:
Функция all(. ) является тем же из следующего:
Расширенная версия
Ответ 3
Это самый эффективный способ узнать, является ли число простым, если у вас есть только несколько запросов. Если вы задаете много чисел, если они просто попробуйте Сито Эратосфена.
Ответ 4
Я думаю, вы хотели закончить цикл for, когда нашли фактор, но не знали, как это сделать, поэтому вы добавили это, пока оно имеет условие. Итак, вот как вы это делаете:
Ответ 5
Ответ 6
Ответ 7
он работал со мной просто отлично: D
Ответ 8
print isPrime (2)
Правда
print isPrime (3)
Правда
print isPrime (9)
False
Интервью на Python: Простые числа
Напишите программу, чтобы составить список всех простых чисел меньше 20. Перед началом важно отметить, что такое простое число. Простое число должно быть положительным целым числом, делящимся ровно на 2 целых числа (1 и само по себе) 1 не является простым числом, хотя существует множество различных способов решения этой проблемы, вот несколько различных подходов.
Напишите программу, чтобы составить список всех простых чисел меньше 20.
Прежде чем начать, важно отметить, что такое простое число.
Хотя существует множество различных способов решения этой проблемы, вот несколько различных подходов.
Подход 1: Для петель
Если вы посмотрите на внутренний цикл for, заключенный в красный прямоугольник ниже, обратите внимание, что, как только isPrime имеет значение False, продолжать итерацию неэффективно. Было бы более эффективно выйти из цикла.
Подход 2: Для петель с разрывом
Подход 3: Для цикла, разрыва и квадратного корня
Сравнение во времени различных подходов
Некоторые методы генерации простых чисел более эффективны. Чтобы показать это, давайте изучим разницу в производительности между подходами, генерирующими простые числа до заданного числа.
Подход 1: Для петель
Подход 2: Для петель с разрывом
Подход 3: Для цикла, разрыва и квадратного корня
Очевидно, что подход 3 является самым быстрым.
Заключительные замечания
Эта статья первоначально появилась в моем блоге medium