Апчих

# Программа 2: Используя решето Эратосфена для каждого числа с оптимизацией

def sieve_of_eratosthenes_optimized(N):

    primes = []

    sieve = [True] * (N+1)

    for num in range(2, N+1):

        if sieve[num]:

            primes.append(num)

            for i in range(num*num, N+1, num):

                sieve[i] = False

    return primes

N = int(input("Введите число N: "))

print("Простые числа от 1 до", N, ":", sieve_of_eratosthenes_optimized(N))