Работа с простыми числами на питоне

Question

На хабре откопал древний код, который ищет простые числа вплоть до указанного числа. У меня условие такое: получить в вводе число, указывающее количество чисел в ответе, т.е., если на вводе будет шестерка, то ожидается нечто такое: [0,1,2,3,4,5] . При этом, мне нужно параллельно проходиться по числам от 1 до бесконечности, пока все ячейки не будут заполнены. Бьюсь не первый час над задачкой. Помогите написать рабочий код. Фрагмент, который откопал, ниже. Как я понял, все четные числа, кроме 2, заменяются на нули, на чем и построен алгоритм.


def prime_num(n):
    n = input("n=") #Искать до ЭТОГО числа включительно
    a = list(range(n+1))  #Числа от 0 до максимального искомого (n)
    a[1] = 0        #Не брать в расчет 1
    list_ = []        #Создание списка для записи ответов

    i = 2
    while i <= n:     #Пока не дойдем до максимального числа (n):
        if a[i] != 0: #Если число не равно нулю:
            list_.append(a[i])
            for j in range(i, n+1, i):
                a[j] = 0
        i += 1
    return list_

После моей попытки подогнать код под себя, я начал получать в ответе все числа подряд после 7 и теперь н могу разобраться в ЭТОМ. Код приведен ниже. В идеале - прошу объяснить работу алгоритма целиком, таким, какой он есть и каким должен быть. Но будет достаточно и готового решения.

def primes(n):
   
    a = list(range(n**2))
    #print(a) # Пофиксить так, чтобы получалось нужное кол-во элементов Изначально - предел отсчета
    a[1] = 0  # Единицу сразу отсекаем, т.к. она делится только на себя и не является простым числом
    list_ = []

    i = 2  # Начне отсчет с двойки
    print(a)
    
    while len(list_) !=n:
       
        if a[i] != 0: #Заменяются все четные числа на нули
            list_.append(a[i])
            
            for j in range(i, n+1, i): 
                #print(f'a[j] {a[j]} , a {a}')
                a[j] = 0
        #print(i, a)
        i += 1
        
            
        
    return(list_)
print(primes(6))

Answer 1

def primes(n):
    lst = [2]
    i = 2
    while len(lst) < n:
        for j in lst:
            if i % j == 0:
                break
        else:
            lst.append(i)
        i += 1
    return lst

print(primes(6))

Answer 2

Думаю, стоит делать так:

Берём распределение простых чисел p[k] ~ k * ln(k) и берём несколько с запасом верхнюю границу.
Запускаем решето Эратосфена для поиска простых.

Альтернативный вариант:

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

БЛОГ НА HUSL

Работа с простыми числами на питоне

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