Множество простых чисел питон

Решето Эратосфена — алгоритм определения простых чисел

Решето Эратосфена – это алгоритм нахождения простых чисел до заданного натурального числа путем постепенного отсеивания составных чисел. Образно говоря, через решето Эратосфена в процессе его тряски проскакивают составные числа, а простые остаются в решете.

Чтобы понять данный алгоритм, вспомним, что числа являются простыми, если делятся только на единицу и самих себя. Первое простое число — это 2, второе простое число — это 3. Теперь начнем рассуждать:

1. Все четные числа, кроме двойки, — составные, т. е. не являются простыми, так как делятся не только на себя и единицу, а также еще на 2.
2. Все числа кратные трем, кроме самой тройки, — составные, так как делятся не только на самих себя и единицу, а также еще на 3.
3. Число 4 уже выбыло из игры, так как делится на 2.
4. Число 5 простое, так как его не делит ни один простой делитель, стоящий до него.
5. Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.

Последний пункт вытекает из того, что сложные числа всегда можно представить как произведение простых. Поэтому если одно сложное число делится на другое сложное, то первое должно делиться на делители второго. Например, 12 делится на 6, делителями которого являются 2 и 3. Число 12 делится и на 2, и на 3.

Алгоритм Эратосфена как раз заключается в последовательной проверке делимости чисел на предстоящие простые числа. Сначала берется первое простое и из ряда натуральных чисел высеиваются все кратные ему. Затем берется следующее простое и отсеиваются все кратные ему и так далее.

При реализации алгоритма Эратосфена на языке программирования есть некоторая сложность. Допустим, мы помещаем натуральные числа до заданного числа N в массив. Далее в процессе выполнения алгоритма будем заменять обнаруженные сложные числа нулями. После выполнения алгоритма те ячейки массива, которые не содержат нули, содержат простые числа, которые выводятся на экран.

Однако индексация массива начинается с нуля, а простые числа начинаются с двойки. Эта проблема решаема, но добавляет сложности в код. Поскольку алгоритм Эратосфена не такой уж простой, легче пренебречь началом и взять массив от 0 до N . Здесь важнее индексы, чем значения элементов. Значениями могут быть логические True , обозначающее простое число, и False , обозначающее сложное число.

В данном примере реализации алгоритма Эратосфена на языке программирования Python список заполняется числами от 0 до N включительно так, что индексы элементов совпадают с их значениями. Далее все непростые числа заменяются нулями:

N = int(input()) # Создается список из значений от 0 до N включительно primes = [i for i in range(N + 1)] # Вторым элементом списка является единица, которую # не считают простым числом. Забиваем ее нулем primes[1] = 0 # Начинаем с 3-го элемента i = 2 while i  N: # Если значение текущей ячейки до этого не было обнулено, # значит в этой ячейке содержится простое число if primes[i] != 0: # Первое кратное ему будет в два раза больше j = i + i while j  N: # и это число составное, # поэтому заменяем его нулем primes[j] = 0 # переходим к следующему числу, # которое кратно i (оно на i больше) j = j + i i += 1 # Избавляемся от всех нулей в списке primes = [i for i in primes if i != 0] print(primes) 

35 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

Источник

Вывести все простые числа в диапазоне 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

Заключение

В этом уроке мы показали, как написать код для печати простых чисел в заданном диапазоне чисел.

Источник

Решето Эратосфена

Данная программа должна вывести все простые числа в заданном диапазоне (от 0 до n ) при помощи алгоритма «Решето Эратосфена».

Решение задачи

1. Принимаем значение определяющее верхнюю границу диапазона и записываем его в переменную n .
2. Инициализируем переменную sieve («решето») множеством чисел от 2 до n .
3. Используем цикл while , который прекратит свою работу, когда множество sieve станет пустым.
4. Примем во внимание тот факт, что минимальное число в этом множестве (на первой итерации это будет 2) всегда простое.
5. Выводим это число на экран.
6. Далее удаляем это число вместе со всеми числами, кратными ему (в заданном диапазоне).
7. Продолжаем это делать, пока множество sieve не станет пустым.
8. Конец

Исходный код

Ниже дан исходный код для вывода всех простых чисел из заданного диапазона при помощи алгоритма под названием «решето Эратосфена». Результаты работы программы также даны ниже.

n = int(input("Введите верхнюю границу диапазона: ")) sieve = set(range(2, n+1)) while sieve: prime = min(sieve) print(prime, end = "\t") sieve -= set(range(prime, n+1, prime))

Объяснение работы программы

1. Пользователь вводит верхнюю границу диапазона, и она записывается в переменную n .
2. Инициализируем переменную sieve множеством всех чисел в диапазоне от 2 до n . Тип «множество» задается функцией set , а все числа диапазона определяются при помощи функции range .
3. Цикл while будет работать, пока множество sieve не станет пустым.
4. Переменная prime инициализируется минимальным значением из множества sieve . Обращаем внимание, что это всегда будет простое число. И это простое число выводится на экран.
5. Затем это число и все числа, кратные ему, удаляются из множества sieve .
6. Пункты 4 и 5 повторяются до тех пор, пока множество sieve не станет пустым, то есть количество элементов в нем станет равно 0.

Результаты работы программы

Пример 1: Введите верхнюю границу диапазона: 10 2 3 5 7 Пример 2: Введите верхнюю границу диапазона: 15 2 3 5 7 11 13

Источник

Есть ли библиотека Python для перечисления простых чисел?

Есть ли в Python библиотечная функция, которая может перечислять простые числа (последовательно)? Я нашел этот вопрос Самый быстрый способ перечислить все простые числа ниже N, но я предпочитаю использовать чью-то надежную библиотеку, чем создавать собственную. Я был бы рад сделать import math; for n in math.primes:

Вопрос, на который вы ссылаетесь, имеет ссылку на библиотеку numpy, которая имеет функцию простых чисел . — person Hunter McMillen &nbsp schedule 11.11.2012

Что это, пожалуйста? import numpy что тогда? docs.scipy.org/doc/numpy/search.html?q= премьер — person Colonel Panic &nbsp schedule 11.11.2012

вам всегда придется устанавливать верхний предел N . и для большого значения N это может занять много времени . — person Joran Beasley &nbsp schedule 11.11.2012

это может быть то, что вы ищете stackoverflow.com/questions / 567222 / . см. Первый ответ (который на самом деле ссылается на code.activestate.com / recipes / 117119) — person Joran Beasley &nbsp 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 и т. Д.

Источник