SANGNT - Thuật toán Sàng nguyên tố

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 0.1s
C# 0.3s
Java 0.3s
Python 3 0.5s
Memory limit: 256M
C# 250M
Java 250M
Python 3 250M
Author:
Hieu Nguyen
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 1
    kietjumper  commented on March 16, 2025, 1:59 p.m. 
    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;


  • -2
    super_god  commented on Oct. 8, 2024, 2:50 a.m.

    hello ae


  • -1
    Phamnhatvuong555  commented on Nov. 30, 2023, 2:43 p.m.

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


  • -1
    neuoavs  commented on Nov. 19, 2023, 7:37 a.m.

    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 ạ


  • -4
    bnbnbn  commented on Dec. 13, 2024, 2:18 p.m.

    cần m giúp à thg ll để tự làm


  • 0
    tahm1302  commented on July 29, 2023, 2:54 a.m.

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


  • 3
    b21dccn441  commented on July 26, 2023, 8:11 a.m.

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