Как сделать простое число в питоне
Обновлено: 06.07.2024
Python Exercises, Practice and Solution: Write a Python function that takes a number as a parameter and check the number is prime or not.
Пример
Вот мой взгляд на проблему:
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)))
Это действительно простой и лаконичный алгоритм, и поэтому он не должен быть чем-то близким к самому быстрому или наиболее оптимальному алгоритму проверки простоты. Он имеет временную сложность O(sqrt(n)). Перейдите здесь , чтобы узнать больше о правильных тестах на простоту и их истории .
Определение простое число или нет
Доброго времени суток. Учусь на курсах автотестера. Программирование начал недавно только осваивать. Помогите разобраться:
Нужно проверить вводимое число на предмет -простое оно или нет. Простое, делиться только на самого себя и на один
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)
Определение простое число или нет
>>> def isProst(x):
… for i in (2,x-1):
… if not x%i:
… return False
… return True
>>> print isProst(4)
False
>>> print isProst(5)
True
>>> print isProst(7)
True
>>> print isProst(10)
False
Описание
Я дам вам некоторые подробности об этой почти эзотерической единственной строке кода, которая проверит простые числа:
Прежде всего, использование range() действительно плохая идея, потому что оно создаст список чисел, который использует много объем памяти. Лучше использовать xrange(), потому что он создает генератор , который должен запомнить только исходные аргументы, которые вы предоставляете, и генерирует каждое число на лету. Если вы используетеPython 3 или выше range() был преобразован в генератор по умолчанию. Кстати, это не самое лучшее решение: пытаться вызвать xrange(n) для некоторого n, так что n > 231-1 (что является максимальным значением для C long) повышает OverflowError. Поэтому лучший способ создать генератор диапазона – это использовать itertools :
На самом деле вам не нужно идти до n , если вы хотите проверить, n – простое число. Вы можете значительно сократить количество проверок и проверять только от 2 до √(n) (квадратный корень из n). Вот пример:
Давайте найдем все делители n = 100 и перечислим их в таблицу:
Существует ли библиотечная функция, которая может перечислять простые числа (в последовательности) в Python?
Я нашел этот вопрос Самый быстрый способ перечислить все простые числа ниже N, но я предпочел бы использовать чью-то надежную библиотеку, чем свернуть свою собственную. Я был бы счастлив сделать import math; for n in math.primes:
Библиотекаgmpy2 имеет функцию next_prime (). Эта простая функция создаст генератор, который обеспечит бесконечный запас простых чисел:
Если вы будете искать простые числа повторно, создание и повторное использование таблицы всех простых чисел ниже разумного предела (скажем, 1 000 000) будет быстрее. Вот еще один пример использования gmpy2 и Сита Эратосфена для создания таблицы простых чисел. primes2 () сначала возвращает простые числа из таблицы, а затем использует next_prime ().
Вы можете настроить table_limit в соответствии с вашими потребностями. Большие значения потребуют больше памяти и увеличат время запуска для первого вызова primes (), но это будет быстрее для повторных вызовов.
Примечание: Я являюсь сопровождающим gmpy2.
SymPy - это еще один выбор. Это библиотека Python для символьной математики. Он предоставляет несколько функций для prime.
Здесь приведены некоторые примеры.
Не существует алгоритма постоянного времени для генерации следующего простого числа; именно поэтому большинство библиотек требуют верхней границы. На самом деле это огромная проблема, которую необходимо решить для цифровой криптографии. RSA выбирает достаточно большие простые числа, выбирая случайное число и проверяя его на примитивность, пока не найдет простое число.
Учитывая произвольное целое число N , единственный способ найти следующее простое число после N состоит в том, чтобы пройти через N+1 до неизвестного простого числа P . простота.
Тестирование на примитивность очень дешево, и есть библиотеки python, которые делают это: алгоритм простых чисел AKS в Python
Учитывая функцию test_prime , чем бесконечный простой итератор будет выглядеть примерно так:
Существует множество эвристик, которые можно использовать для ускорения процесса. Например, пропустить четные числа или числа, кратные 2,3,5,7,11,13 и т. д..
В этом руководстве мы обсудим, как получить простой множитель данного числа с помощью программы разложения числа в Python. Все мы знакомы с простыми числами – это числа, которые можно разделить на единицу или на себя. Например – 1, 2, 3, 5, 7, 11, 13, ……
Нахождение всех простых множителей числа
Например: 330 = 2 × 3 × 5 × 11.
Прежде чем писать программу на Python, давайте разберемся со следующими догадками.
- 1-я гипотеза – может быть хотя бы один простой множитель, который будет меньше √n в случае, если n не является простым числом.
Доказательство. Существуют два больших числа sqrt(n), их произведение также должно делить n, но оно будет превышать n, что противоречит нашему предположению. Таким образом, не может быть более одного простого множителя n, большего, чем sqrt(n).
Давайте посмотрим на следующий шаг, чтобы выполнить такую операцию.
- 2-я гипотеза – может быть более 1 простого множителя n больше, чем sqrt(n).
Доказательство. Предположим, что есть два больших числа sqrt(n), тогда их произведение также должно делить n, но оно будет больше n, что противоречит нашему предположению. Таким образом, не может быть более одного простого множителя n, большего, чем sqrt(n).
Давайте посмотрим на следующий шаг, чтобы выполнить такую операцию.
Пример – программа Python для печати простых множителей.
В приведенном выше коде мы импортировали математический модуль. Функция prime_factor() отвечает за печать составного числа. Сначала мы получаем четные числа; после этого все оставшиеся простые множители должны быть нечетными. В цикле for число должно быть нечетным, поэтому мы увеличили i на два. Цикл for будет вычислять квадратный корень n раз.
Давайте разберемся в следующем свойстве составных чисел.
Каждое составное число имеет хотя бы один простой множитель, меньший или равный квадратному корню.
Программа будет работать следующим образом:
- На первом шаге найдем наименьший простой множитель i.
- Вхождение i будет удалено из n путем многократного деления n на i.
- Повторим оба вышеуказанных шага для деления n и i = i + 2. Оба шага будут повторяться до тех пор, пока n не станет либо 1, либо простым числом.
Давайте разберемся в другом примере, где мы находим наибольший простой множитель данного числа.
Пример – 2: Программа Python для определения наибольшего простого множителя заданного числа.
Оператор == проверяет, указывают ли две ссылки на один и тот же объект или нет. .equals() проверьте фактическое содержимое строки (значение).
Обратите внимание, что метод .equals() принадлежит классу Object (суперкласс всех классов). Вам необходимо переопределить его в соответствии с вашим требованием к классу, но для String оно уже реализовано и проверяет, имеет ли две строки одно и то же значение.
- Случай 1 Причина: строка литералы, созданные без нуля, хранятся в пуле строк в области перментонов кучи. Таким образом, оба s1 и s2 указывают на один и тот же объект в пуле.
- Случай 2 Причина. Если вы создаете объект String с использованием ключевого слова new , ему выделяется отдельное пространство в куче.
Вам нужно проверить все числа от 2 до n-1 (до sqrt (n) на самом деле, но нормально, пусть это будет n). Если n делится на любое из чисел, оно не является простым. Если число является простым, распечатайте его.
Вы можете написать то же намного короче и больше pythonic:
Как я уже сказал, было бы лучше проверить делители не от 2 до n -1, но от 2 до sqrt (n):
Для небольших чисел, таких как 101, это не имеет значения, но для 10 ** 8 разница будет действительно большой.
Вы можете улучшить его немного больше, увеличивая диапазон, который вы проверяете на 2, и тем самым проверяете нечетные числа. Так же:
Как и в первом цикле, выбраны нечетные числа, во втором цикле нет необходимости проверять четными числами, поэтому 'i 'может начинаться с 3 и пропускаться на 2.
Отличная работа, но почему вы игнорируете номер 1? Одно не считается простым числом. Пожалуйста, просмотрите эту статью primes.utm.edu/notes/faq/one.html – Mouneer 4 July 2015 в 18:38
Измените range(1,101) на range(2,101) , и код будет идеальным. Давайте не будем забывать, что 1 не является простым. – Akash Adhikari 1 November 2017 в 14:24
Добавляя к принятому ответу, дальнейшая оптимизация может быть достигнута путем использования списка для хранения простых чисел и их печати после генерации.
Самый быстрый & amp; наилучшая реализация пропусков простых чисел:
Вот другой подход, который торгует пространство для более быстрого поиска. Это может быть быстрее всего.
Не могли бы вы подробнее рассказать о своем ответе, добавив немного подробного описания вашего решения? – abarisone 19 June 2015 в 07:09
Вы заканчиваете цикл слишком рано. После того, как вы проверили все возможности в теле цикла for, а не сломались, число будет простым. Поскольку одно не простое, вам нужно начинать с 2:
. В более быстром решении вы пытаетесь разделить на простые числа, которые меньше или равны корню числа, которое вы тестируете. Это может быть достигнуто путем запоминания всех простых чисел, которые вы уже нашли. Кроме того, вам нужно только проверить нечетные числа (кроме 2). Вы можете поместить полученный алгоритм в генератор, чтобы вы могли использовать его для хранения простых в контейнере или просто распечатывать их:
Как вы можете видеть, нет необходимости вычислять квадратный корень, быстрее хранить квадрат для каждого простого числа и сравнивать каждый делитель с этим числом.
Нет, вы ошибаетесь, конечно. continue здесь не поможет. Пожалуйста, напишите решение wit continue , если вы считаете, что правы – Igor Chubin 23 July 2012 в 21:32
Печать n простых чисел с использованием python:
Я сторонник того, чтобы не принимать лучшее решение и тестировать его. Ниже приведены некоторые изменения, которые я сделал для создания простых классов примеров, как с помощью @ igor-chubin, так и с @ user448810. Прежде всего позвольте мне сказать, что это отличная информация, спасибо вам, ребята. Но я должен признать @ user448810 за его умное решение, которое оказалось самым быстрым на сегодняшний день (из тех, что я тестировал). Так тебе, сэр! Во всех примерах я использую значения 1 миллион (1 000 000) в виде n.
Пожалуйста, не стесняйтесь попробовать код.
Метод 1, описанный Игорем Чубиным:
Тест: более 272 секунд
Метод 2 как описано Игорем Чубиным:
Контрольный показатель: 73.3420000076 секунд
Метод 3, описанный Игорем Чубиным:
Контрольный показатель: 11.3580000401 секунд
Метод 4, описанный Игорем Чубиным:
Контрольный показатель: 8.7009999752 секунд
Метод 5, как описано пользователем448810 (что, по моему мнению, было довольно умно):
Benchmark: 1.12000012398 секунд
Примечания: Решение 5, указанное выше (как было предложено пользователем448810), оказалось самым быстрым и честным тихим творческим и умным. Я люблю это. Спасибо, ребята !!
EDIT: О, и, кстати, я не чувствовал необходимости импортировать математическую библиотеку для квадратного корня из значения, поскольку эквивалент просто (n ** 0,5). В противном случае я не редактировал много других, а затем возвращал значения в массив и возвращал массив. Кроме того, было бы, вероятно, немного более эффективно хранить результаты в файле, чем подробные, и могло бы сэкономить много на памяти, если бы это было просто по одному, но стоило бы немного больше времени из-за записи на диск. Я думаю, что всегда есть место для улучшения. Так что, надеюсь, код имеет смысл.
Сначала мы находим коэффициент этого числа
Сценарий для проверки простого или нет
Сценарий для печати всего простого числа до n
Вот простейшая логика для начинающих, чтобы получить простые числа:
Вот простая и интуитивно понятная версия проверки, является ли это простым в функции RECURSIVE! :) (Я сделал это как домашнее задание для класса MIT). В python он работает очень быстро до 1900 года. Если вы попробуете более 1900, вы получите интересную ошибку :) (Хотелось бы проверить, сколько номеров компьютер может управлять?)
Конечно . если вам нравятся рекурсивные функции, этот маленький код может быть обновлен со словарем, чтобы серьезно увеличить его производительность и избежать этой смешной ошибки. Вот простой вариант обновления 1 уровня с интеграцией MEMORY:
Вот резули, где я напечатал последние 100 простых чисел.
время и дата: 2013-10-15 13: 32: 11.674448
Имеются 9594 простых чисел, до 100000
[99991, 99989, 99971, 99961, 99929, 99923, 99907, 99901, 99881, 99877, 99871, 99859, 99839, 99833, 99829, 99823, 99817, 99809, 99793, 99787, 99767, 99761, 99733, 99721, 99719 , 99713, 99709, 99707, 99689, 99679, 99667, 99661, 99643, 99623, 99611, 99607, 99581, 99577, 99571, 99563, 99559, 99551, 99529, 99527, 99523, 99497, 99487, 99469, 99439, 99431 , 99409, 99401, 99397, 99391, 99377, 99371, 99367, 99349, 99347, 99317, 99289, 99277, 99259, 99257, 99251, 99241, 99233, 99223, 99191, 99181, 99173, 99149, 99139, 99137, 99133 , 99131, 99119, 99109, 99103, 99089, 99083, 99079, 99053, 99041, 99023, 99017, 99013, 98999, 98993, 98981, 98963, 98953, 98947, 98939, 9892 9, 98927, 98911, 98909, 98899, 98897] .
Для его вычисления потребовался ваш компьютер 0: 00: 40.871083
Так что для моего ноутбука i7 потребовалось 40 секунд для его расчета. :)
Читайте также: