Thuật toán Sàng nguyên tố - LCOJ: Luyện Code Online Judge

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

Đ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ả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, 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

Output #1

2 3

Input #2

Output #2

2 3 5 7

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

Bình luận

Please read the guidelines before commenting.

include <stdio.h>

#include <stdlib.h>
#include <math.h>
#include <stdbool.h>

int main(void) {
    int n;
    int i, j;
    scanf("%d", &n);
    bool *a = malloc((n+5) * sizeof(bool));
    for (i = 0; i < n+5; i++){
        a[i] = 1;
    }
    // Sang nguyen to
    a[0] = 0; a[1] = 0;
    for (i = 2; i <= sqrt(n); i++){
        if (a[i]){
            for (j = i*i; j<= n; j+=i){
                a[j] = 0;
            }
        }
    }
    for (i = 0; i <= n; i++){
        if (a[i]) printf("%d ", i);
    }
    return 0;
}

-1

trandaiquangdeptrai2011 đã bình luận lúc 1, Tháng 11, 2025, 13:58

helo ae

1

Mizu đã bình luận lúc 17, Tháng 10, 2025, 12:42

Bài này nếu chạy trong 0.1s (rất ngắn) thì mọi người có thể dùng thử thuật toán ssàng Eratosthenes nhé mình làm rồi và AC hết (C++)

-1

VHung đã bình luận lúc 25, Tháng 8, 2025, 7:31

t thắc mắc sao xài chương trình con nó lại lỗi 4 test nhỉ

0

Sheya đã bình luận lúc 4, Tháng 4, 2026, 10:59

AI biết á,hỏi thử đi

-2

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

hello ae

-3

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 ạ

-3

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 ạ

-2

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 ạ