Đếm số nguyên tố - LCOJ: Luyện Code Online Judge

MK119SNT - Đếm số nguyên tố

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

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

Cho hai số nguyên dương ~L ≤ R~. Hãy đếm xem trong đoạn ~[L, R]~ có bao nhiêu số nguyên tố.

Input

Dòng đầu ghi số nguyên dương ~T~ là số bộ test;
~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~L ≤ R~ cách nhau bởi một dấu cách.

Giới hạn:

~1 ≤ T ≤ 10^2, 1 ≤ L ≤ R ≤ 10^6~.

Output

Với mỗi cặp số ~L~ và ~R~, ghi ra trên một dòng số số nguyên tố trong đoạn ~[L, R]~.

Sample

Input #1

2
2 3
10 15

Output #1

2
2

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

Bình luận

Please read the guidelines before commenting.

hint

vì n <= 1e6 và ta phải trả lời trên nhiều truy vấn nên ta phải sử dụng sàng nguyên tố đến 1e6 để check snt
và dùng prefix sum để đếm số nguyên tố từ 1 -> i
với mỗi truy vấn in ra $$f[r] - f[l - 1]$$

code tham khảo (c++)

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000001
bool nt[MAX];
void sang(int n = MAX) {
    memset(nt, 1, sizeof nt); 
    nt[0] = nt[1] = 0; 
    for(int i = 2; i < sqrt(n); ++i) 
        if(nt[i]) for(int j = i*i; j < n; j+=i) 
            nt[j] = 0; 
}
int f[MAX]; 
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    sang(); 
    for(int i = 2; i < MAX; ++i) f[i] = f[i - 1] + nt[i]; 
    int t; 
    cin >> t; 
    while(t--) {
        int l, r; 
        cin >> l >> r; 
        cout << f[r] - f[l - 1] << '\n';
    }
}

0

trunghieu88007 đã bình luận lúc 14, Tháng 1, 2026, 13:55

9/10 TLE :((

include <bits/stdc++.h>

using namespace std;

int main(){ ios::syncwithstdio(false); cin.tie(nullptr);

const int MAXN = 1000000;
vector<bool> isPrime(MAXN+1, true);
isPrime[0] = false;
isPrime[1] = false;

for(int i = 2; i * i <= MAXN; i++){
    if(isPrime[i]){
        for(int j = i * i; j <= MAXN; j += i){
            isPrime[j] = false;
        }
    }
}

vector<int> pref(MAXN+1, 0);
for(int i = 1; i <= MAXN; i++){
    pref[i] = pref[i-1] + (isPrime[i] ? 1 : 0);
}

int T;
cin >> T;
while(T--){
    int L, R;
    cin >> L >> R;
    if(L < 1) L = 1;
    int result = pref[R] - pref[L-1];
    cout << result << "\n";
}

return 0;

}

0

BoCow2808 đã bình luận lúc 18, Tháng 9, 2025, 4:44

vl sao bị cả OLE lầ sao mn, lần đầu bị luôn

-1

BoCow2808 đã bình luận lúc 18, Tháng 9, 2025, 4:42

vl sao bị cả OLE lầ sao mn, lần đầu bị luôn

2

K35Ti_Quoc_Anh đã bình luận lúc 20, Tháng 7, 2025, 3:43

my code https://gist.github.com/Uiiis/95d825d24c57204594964e2007166de0

2

0988440189 đã bình luận lúc 19, Tháng 4, 2025, 10:16

Nếu bài này ae chỉ sàng số nguyên tố rồi duyệt đoạn từ [l->R]xem có bao nhiêu sô nguyên tố thì chắc chắn bị TLE , Ae nên kết hợp tư tưởng prefixSum nhé .Kiểu anh sàng xong thì duyệt thêm 1 vòng for cho tập S , S sẽ chứa số lượng số nguyên tố trong đoạn 11 đến i (i<=1e6) .S[1]=0,S[2]=1(chứa số 2),S[3]=2 (chứa 2,3) ,S[4]=2 (chứa 2 ,3) Vậy công thức để lưu S[i] là nếu xét phần tử i hiện tại mà nó là số nguyên tố thì S[i]=S[i-1]+1 , còn không thì lưu S[i]=S[i-1]... FAN MU muôn năm...

-3

tuananh2605 đã bình luận lúc 3, Tháng 10, 2024, 14:20

sao toàn 4/10 6 test quá tg

-2

bads đã bình luận lúc 25, Tháng 9, 2024, 3:43

toàn chạy quá thời gian

2

fishsauce đã bình luận lúc 16, Tháng 2, 2024, 16:20

Bạn sử dụng sàng số nguyên tố nhé

5

kdat38 đã bình luận lúc 7, Tháng 12, 2023, 4:25

sàng+prefix sum