Поиск N первых простых чисел. Код ушёл в бесконечный цикл

Рейтинг: 0Ответов: 1Опубликовано: 23.07.2023

я написала код по задаче:

Напишите программу, которая выводит на экран первые N простых чисел.

Входные данные
Входная строка содержит число N .

Выходные данные
Программа должна вывести первые N простых чисел в одной строке, 
разделив их пробелом.

Примеры
входные данные
10
выходные данные
2 3 5 7 11 13 17 19 23 29

Код:

def is_prime(n):
    q=2
    while q*q<=n:
        if n%q==0:
            return False
        q+=1
    return True
n=int(input()) 
ans=[2] 
q=3
while len(ans)<n:
    if is_prime(q):
        ans.append(q) 
        q+=2 
print(*ans)

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

python алгоритм простые-числа
Источник: Stack Overflow на русском

Ответы

▲ 4Принят

q ведь надо увеличивать независимо от простоты

while len(ans)<n:
    if is_prime(q):
        ans.append(q) 
    q+=2

Кроме того, накопление с постоянным наращиванием списка излишне, можно сразу выводить

n=int(input())
prime_count = 1
print(2, end = ' ')
q = 3
while prime_count<n:
    if is_prime(q):
        print(q, end = ' ')
        prime_count += 1
    q+=2

Вариант с использованием уже найденных простых чисел:

n=int(input())
ans = [2]*n
prime_count = 1
q=3
while prime_count < n:
    idx = 0
    isprime = True
    while ans[idx]*ans[idx]<=q:
        if q % ans[idx] == 0:
            isprime = False
            break
        idx += 1
    if isprime:
        ans[prime_count] = q
        prime_count += 1
    q+=2
print(*ans)