Перебор простых чисел

Question

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

Answer 1

import math
def prime_num():
    nm = 2
    while True:
        sq = math.ceil(nm ** 1 / 2)
        for i in range(2, sq + 1):
            if (nm % i) == 0:
                break
        else:
            yield nm
        nm += 1

for i in prime_num(): # Бесконечно генерирует простые числа начиная с 2
    # do smth with i
    ...

Также можно использовать алгоритм решета Эратосфена если нужны простые числа до определённого числа

from functools import reduce

n = 100 # Простые числа до 100

primes = reduce(lambda r, x: r - set(range(x**2, n, x)) if x in r else r, range(2, int(n**0.5) + 1), set(range(2, n)))

print(primes)
# {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}

Answer 2

как вариант, можно использовать библиотеки, например gmpy2, примерно так:

next_prime(x) returns the next probable prime number > x

import gmpy2

p = 1  # простое число
while True:
    # ваши действия с числом
    if  # условие выхода из цикла
        break
    p = gmpy2.next_prime(p)

БЛОГ НА HUSL

Перебор простых чисел

Ответы (2 шт):