SANGNT - Thuật toán Sàng 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: 0.1s
C# 0.3s
Java 0.3s
Python 3 0.5s
Giới hạn bộ nhớ: 256M
C# 250M
Java 250M
Python 3 250M
Tác giả:
Hieu Nguyen
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Một số nguyên dương ~n > 1~ được gọi là số nguyên tố nếu nó không có ước nguyên dương ngoài ~1~ và chính nó (hay không có ước nguyên dương thực sự khác ~1~).

Yêu cầu:

Cho số nguyên dương ~n~, hãy liệt kê tất cả các số nguyên tố nhỏ hơn hoặc bằng ~n~.

Input

  • Gồm một số nguyên dương ~n~.

Giới hạn:

  • ~1 ≤ n ≤ 10^6~.

Output

  • Ghi ra trên một dòng các số nguyên tố nhỏ hơn hoặc bằng ~n~, các số được ghi ra theo thứ tự tăng dần, hai số liên tiếp cách nhau một dấu cách.

Sample

Input #1
3
Output #1
2 3
Input #2
10
Output #2
2 3 5 7

Problem source: Chuyên Sơn La Online Judge

Bình luận

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


  • 1
    kietjumper  đã bình luận lúc 16, Tháng 3, 2025, 13:59 
    const int maxn = 1000000 + 5; //10^6 + 5
bool d[maxn];
void sang(int n)
{
    for (int i = 2; i <= n; i++)
    {
        d[i] = true;
    }
    for (int i = 2; i * i <= n; i++) 
    {
        if (d[i]) 
        {
            for (int j = i * 2; j <= n; j += i)
            {
                d[j] = false;
            }
        }
    }
}

    trong int main(): if(d[i]) cout<< i;


  • -1
    super_god  đã bình luận lúc 8, Tháng 10, 2024, 2:50

    hello ae


  • -1
    Phamnhatvuong555  đã bình luận lúc 30, Tháng 11, 2023, 14:43

    ai có code python cho mình tham khảo với ạ


  • -1
    neuoavs  đã bình luận lúc 19, Tháng 11, 2023, 7:37

    Anh ơi bên C++ có 0.1s giới hạn thôi hả anh. Anh có thể tăng lên không ạ


  • -5
    bnbnbn  đã bình luận lúc 13, Tháng 12, 2024, 14:18

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 0
    tahm1302  đã bình luận lúc 29, Tháng 7, 2023, 2:54

    bạn nào AC python cho mình tham khảo với


  • 4
    b21dccn441  đã bình luận lúc 26, Tháng 7, 2023, 8:11

    bài này lên tăng thời gian cho Java anh ạ