# Программа 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))