In ra các số nguyên tố từ 1 đến n (sàng số nguyên tố)

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài

In ra các số nguyên tố từ 1 đến n sử dụng sàng số nguyên tố


Ràng buộc: n đến 10^6


Input 01:
10
Output 01:
2 3 5 7
Input 02:
100
Output 02:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    hoangan_2013  đã bình luận lúc 9, Tháng 6, 2025, 14:19

    nhớ dùng sàng số nguyên tố bằng cách này nè dễ hiểu

    Ý tưởng của sàng Eratosthenes:

    Tạo một mảng isPrime[] có kích thước n + 1, gán tất cả các giá trị là true, ngoại trừ isPrime[0] và isPrime[1] là false.

    Với mỗi số i từ 2 đến sqrt(n):

    Nếu i là số nguyên tố (tức isPrime[i] == true), đánh dấu tất cả bội số của i (từ i*i đến n) là false.

    In ra tất cả các i từ 2 đến n mà isPrime[i] == true.