Nhập giá trị n từ bàn phím

n = int(input())

Bước 1: Khởi tạo danh sách đánh dấu. Mặc định coi tất cả là số nguyên tố (True)

Danh sách có n + 1 phần tử để chứa được chỉ số từ 0 đến n

snt = [True] * (n + 1)

Bước 2: Loại bỏ số 0 và số 1 vì chúng không phải số nguyên tố

snt[0] = snt[1] = False

Bước 3: Thuật toán Sàng Eratosthenes

Chỉ cần quét đến căn bậc hai của n để tối ưu tốc độ

for i in range(2, int(n*0.5) + 1):
if snt[i]: # Nếu i là số nguyên tố
# Loại bỏ các bội số của i bắt đầu từ ii
for j in range(i * i, n + 1, i):
snt[j] = False

Bước 4: Lọc các số còn giữ giá trị True để đưa vào kết quả

kq = []
for i in range(2, n + 1):
if snt[i]:
kq.append(i)

Bước 5: In kết quả, dùng dấu * để trải các phần tử ra

print(*kq)