Вывести ряд простых чисел в python
Я пытаюсь изучить Python-программирование, и я довольно новичок в этом. У меня возникали проблемы с печатью ряда простых чисел от одной до сотни. Я не могу понять, что не так с моим кодом. Вот что я написал; он печатает все нечетные числа вместо простых чисел:
for num in range(1,101): for i in range(2,num): if (num%i==0): break else: print(num) break 31 ответ
Вам нужно проверить все числа от 2 до n-1 (на самом деле до sqrt (n), но хорошо, пусть это будет n). Если n делится на любое из чисел, оно не простое. Если число простое, выведите его.
for num in range(2,101): prime = True for i in range(2,num): if (num%i==0): prime = False if prime: print num Вы можете написать то же самое намного короче и более питонично:
for num in range(2,101): if all(num%i!=0 for i in range(2,num)): print num Как я уже сказал, было бы лучше проверять делители не от 2 до n-1, а от 2 до sqrt (n):
import math for num in range(2,101): if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)): print num Для небольших чисел, таких как 101, это не имеет значения, но для 10 ** 8 разница будет очень большой.
Вы можете немного улучшить его, увеличив диапазон, который вы проверяете, на 2 и, таким образом, проверяя только нечетные числа. Вот так:
import math print 2 for num in range(3,101,2): if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)): print num Так как в первом цикле выбраны нечетные числа, во втором цикле нет необходимости проверять четные числа, поэтому значение ‘i’ можно начинать с 3 и пропускать до 2.
import math print 2 for num in range(3,101,2): if all(num%i!=0 for i in range(3,int(math.sqrt(num))+1, 2)): print num Отличная работа, но почему вы игнорируете номер 1? Один не считается простым числом. Пожалуйста, смотрите эту статью primes.utm.edu/notes/faq/one.html
Измените свой range(1,101) на range(2,101) и код будет идеальным. Давайте не будем забывать, 1 не простое число.
break завершает цикл, в котором он находится. Таким образом, вы только проверяете, делится ли он на 2, давая вам все нечетные числа.
for num in range(2,101): for i in range(2,num): if (num%i==0): break else: print(num) что, как говорится, есть намного лучшие способы найти простые числа в python, чем это.
for num in range(2,101): if is_prime(num): print(num) def is_prime(n): for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return True Вот страница из документа Python, описывающая break / continue , с примером печати простых чисел! docs.python.org/tutorial/controlflow.html (раздел 4.4)
Нет, вы не правы, конечно. continue здесь не поможет. Пожалуйста , напишите остроумие решения continue , если вы думаете , что вы правы
Вместо пробного разделения лучший подход, изобретенный греческим математиком Эратосфеном более двух тысяч лет назад, заключается в том, чтобы просеять, многократно изгоняя кратные простые числа.
Начните с составления списка всех чисел от 2 до максимального желаемого числа n. Затем многократно принимайте наименьшее непересекающееся число и вычеркивайте все его кратные числа; числа, которые остаются непересекающимися, являются просторными.
Например, рассмотрите числа, меньшие 30. Сначала 2 обозначается как простой, затем 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 и 30 являются вычеркнуто. Следующие 3 обозначены как простые, затем 6, 9, 12, 15, 18, 21, 24, 27 и 30 вычеркнуты. Следующий штрих равен 5, поэтому 10, 15, 20, 25 и 30 вычеркнуты. И так далее. Цифры остаются неизменными: 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29.
def primes(n): sieve = [True] * (n+1) for p in range(2, n+1): if (sieve[p]): print p for i in range(p, n+1, p): sieve[i] = False Оптимизированная версия сита обрабатывает 2 отдельно и решает только нечетные числа. Кроме того, поскольку все композиты, меньшие квадрата текущего штриха, пересекаются меньшими штрихами, внутренний цикл может начинаться с p ^ 2 вместо p, а внешний цикл может останавливаться у квадратного корня n. Я оставлю оптимизированную версию для работы.
Вывести все простые числа в диапазоне Python – пошаговый алгоритм
Простое число — это натуральное число, которое больше 1 и не имеет положительного делителя, кроме 1 и самого себя, например 2, 3, 5, 7, 11, 13 и так далее.
Пользователю даются два целых числа, нижнее значение и верхнее значение. Задача состоит в том, чтобы написать программу Python для вывода всех простых чисел в заданном интервале (или диапазоне).
Чтобы напечатать все простые числа в заданном интервале, пользователь должен выполнить следующие шаги:
- Шаг 1: Переберите все элементы в заданном диапазоне.
- Шаг 2: Проверьте для каждого числа, есть ли у него какой-либо множитель между 1 и самим собой.
- Шаг 3: Если да, то число не простое, и оно перейдет к следующему числу.
- Шаг 4: Если нет, то это простое число, и программа распечатает его и проверит следующее число.
- Шаг 5: Цикл прервется, когда будет достигнуто верхнее значение.
Пример: код Python для печати простого числа в заданном интервале.
# First, we will take the input: lower_value = int(input("Please, Enter the Lowest Range Value: ")) upper_value = int(input("Please, Enter the Upper Range Value: ")) print("The Prime Numbers in the range are: ") for number in range(lower_value, upper_value + 1): if number > 1: for i in range(2, number): if(number % i) == 0: break else: print(number) Please, Enter the Lowest Range Value: 14 Please, Enter the Upper Range Value: 97 The Prime Numbers in the range are: 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Заключение
В этом уроке мы показали, как написать код для печати простых чисел в заданном диапазоне чисел.
Есть ли библиотека Python для перечисления простых чисел?
Есть ли в Python библиотечная функция, которая может перечислять простые числа (последовательно)? Я нашел этот вопрос Самый быстрый способ перечислить все простые числа ниже N, но я предпочитаю использовать чью-то надежную библиотеку, чем создавать собственную. Я был бы рад сделать import math; for n in math.primes:
Вопрос, на который вы ссылаетесь, имеет ссылку на библиотеку numpy, которая имеет функцию простых чисел . — person Hunter McMillen   schedule 11.11.2012
Что это, пожалуйста? import numpy что тогда? docs.scipy.org/doc/numpy/search.html?q= премьер — person Colonel Panic   schedule 11.11.2012
вам всегда придется устанавливать верхний предел N . и для большого значения N это может занять много времени . — person Joran Beasley   schedule 11.11.2012
это может быть то, что вы ищете stackoverflow.com/questions / 567222 / . см. Первый ответ (который на самом деле ссылается на code.activestate.com / recipes / 117119) — person Joran Beasley   schedule 11.11.2012
Ответы (4)
Другой вариант — SymPy. Это библиотека Python для символической математики. Он предоставляет несколько функций для прайма.
isprime(n) # Test if n is a prime number (True) or not (False). primerange(a, b) # Generate a list of all prime numbers in the range [a, b). randprime(a, b) # Return a random prime number in the range [a, b). primepi(n) # Return the number of prime numbers less than or equal to n. prime(nth) # Return the nth prime, with the primes indexed as prime(1) = 2. The nth prime is approximately n*log(n) and can never be larger than 2**n. prevprime(n, ith=1) # Return the largest prime smaller than n nextprime(n) # Return the ith prime greater than n sieve.primerange(a, b) # Generate all prime numbers in the range [a, b), implemented as a dynamically growing sieve of Eratosthenes. >>> import sympy >>> >>> sympy.isprime(5) True >>> list(sympy.primerange(0, 100)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] >>> sympy.randprime(0, 100) 83 >>> sympy.randprime(0, 100) 41 >>> sympy.prime(3) 5 >>> sympy.prevprime(50) 47 >>> sympy.nextprime(50) 53 >>> list(sympy.sieve.primerange(0, 100)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] Библиотека gmpy2 имеет функцию next_prime (). Эта простая функция создаст генератор, который обеспечит бесконечный запас простых чисел:
import gmpy2 def primes(): n = 2 while True: yield n n = gmpy2.next_prime(n) Если вы будете многократно перебирать простые числа, создание и повторное использование таблицы всех простых чисел ниже разумного предела (скажем, 1000000) будет быстрее. Вот еще один пример использования gmpy2 и решета Эратосфена для создания таблицы простых чисел. primes2 () сначала возвращает простые числа из таблицы, а затем использует next_prime ().
import gmpy2 def primes2(table=None): def sieve(limit): sieve_limit = gmpy2.isqrt(limit) + 1 limit += 1 bitmap = gmpy2.xmpz(3) bitmap[4 : limit : 2] = -1 for p in bitmap.iter_clear(3, sieve_limit): bitmap[p*p : limit : p+p] = -1 return bitmap table_limit=1000000 if table is None: table = sieve(table_limit) for n in table.iter_clear(2, table_limit): yield n n = table_limit while True: n = gmpy2.next_prime(n) yield n Вы можете настроить table_limit в соответствии со своими потребностями. Большие значения потребуют больше памяти и увеличат время запуска для первого вызова primes (), но это будет быстрее для повторных вызовов. Примечание: я сопровождаю gmpy2.
В документации для gmpy2 сказано: next_prime (x) возвращает следующее вероятное простое число ›x. Текст, выделенный жирным шрифтом в соответствии с документом. Я думаю, что это нужно прояснить. — person Dave Rove; 18.09.2018
Задав этот вопрос, я написал оболочку Python вокруг primesieve библиотеки C ++, которая впоследствии была принята сопровождающим primesieve. https://github.com/kimwalisch/primesieve-python
>>> from primesieve import * # Generate a list of the primes below 40 >>> generate_primes(40) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] # Generate a list of the primes between 100 and 120 >>> generate_primes(100, 120) [101, 103, 107, 109, 113] # Generate a list of the first 10 primes >>> generate_n_primes(10) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] # Generate a list of the first 10 starting at 1000 >>> generate_n_primes(10, 1000) [1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061] # Get the 10th prime >>> nth_prime(10) 29 # Count the primes below 10**9 >>> count_primes(10**9) 50847534 Не существует алгоритма постоянного времени для генерации следующего простого числа; вот почему для большинства библиотек требуется верхняя граница. На самом деле это огромная проблема, которую необходимо было решить для цифровой криптографии. RSA выбирает достаточно большие простые числа, выбирая случайное число и проверяя простоту, пока не найдет простое число. Учитывая произвольное целое число N , единственный способ найти следующее простое число после N — это пройти через N+1 до неизвестного простого P , проверяя простоту. Тестирование на простоту очень дешево, и для этого существуют библиотеки Python: алгоритм AKS Primes в Python Для функции test_prime итератор с бесконечным числом простых чисел будет выглядеть примерно так:
class IterPrimes(object): def __init__(self,n=1): self.n=n def __iter__(self): return self def next(self): n = self.n while not test_prime(n): n += 1 self.n = n+1 return n Есть много эвристик, которые можно использовать для ускорения процесса. Например, пропускайте четные числа или числа, делящиеся на 2, 3, 5, 7, 11, 13 и т. Д.
Составить список простых чисел
Однако хотелось бы составить алгоритм, который выводил бы список простых чисел. Например, с помощью range() перебирает числа от 1 до 100 и определяет среди них простое и заносит их в список. Пробовал сам, но получалась фигня какая-то Буда благодарен вашим идеям
Решето Эратосфена: вернуть список простых чисел на заданном интервале
Помогите реализовать функцию. Создать функцию, которая принимает два параметра — два числа, и.
Составить новый список чисел из встречающихся в исходном списке максимальное число разю
Составить новый список чисел, отсортированных по возрастанию, из чисел переданного списка.
Из исходного списка целых чисел сформируйте два списка: список четных чисел В и список нечетных чисел С
2. Из исходного списка целых чисел сформируйте два списка: список четных чисел В и.
Составить список простых чисел вида 2n+1
Составить список простых чисел вида 2n+1. Написать функцию для выбора k-го члена этого списка. (В.
SalavatGood,
1) подход не верен, зачем проверять дальше если сразу знаем что не простое? Как только разделилось на что-то кроме 1 и себя -сразу возвращаем False, все циклы прерываем
2) вынеси определение простоты в отдельную функцию, тогда будет просто реализовать то, что ты хочешь — вызывая ее для разных чисел из range