Nguyên tố sinh đôi - LCOJ: Luyện Code Online Judge

TWINS - Nguyên tố sinh đôi

Đ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

Trong lý thuyết số, hai số nguyên tố ~p~ và ~q~ được gọi là cặp số nguyên tố sinh đôi nếu ~q - p=2~. Ví dụ: các cặp số ~(3,5),(5,7),(11,13),(17,19)~ là các cặp sinh đôi. Trong trường hợp tổng quát, với số nguyên dương ~k~ cho trước, cặp số nguyên tố ~p~ và ~q~ được gọi là sinh đôi nếu ~q - p=k~. Ví dụ: với ~k=4~ cặp số nguyên tố ~(3,7)~ được gọi là sinh đôi.

Yêu cầu: Cho ~n~ và ~k\ (1≤k≤n≤10^6)~. Hãy xác định số cặp sinh đôi trong phạm vi từ ~1~ đến ~n~ (thỏa mãn ~q - p=k~).

Input

Một dòng duy nhất chứa hai số nguyên ~n~ và ~k~.

Giới hạn:

Subtask #1: 80% số điểm có ~n≤10^4~;
Subtask #2: 20% số điểm còn lại có ~10^4< n≤10^6~.

Output

Một số nguyên là số lượng cặp sinh đôi tìm được.

Sample

Input #1

17 2

Output #1

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

Bình luận

Please read the guidelines before commenting.

spoil!

ý tưởng: 
tạo 1 mảng gồm các số nt từ 1 đến n
dùng 2 con trỏ kiểm tra điều kiện nếu bé hơn tăng con trỏ phải 
nếu đúng tăng đếm 
**lưu ý: luôn tăng con trỏ trái**

code tham khảo (c++)

    #include <bits/stdc++.h>

    using namespace std;

    const int lim = 1e6;
    bool nt[lim];
    void sang(int n = lim) {
        memset(nt, true, sizeof nt);
        nt[0] = nt[1] = false;
        for(int i = 2; i*i <= n; ++i)
            if(nt[i])
                for(int j = i*i; j <= n; j += i) nt[j] = false;
    }
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

        sang();
        int n, k;
        cin >> n >> k;
        vector<int> res;
        res.push_back(-1);
        for(int i = 2; i <= n; ++i) if(nt[i]) res.push_back(i);
        int x = 1, y = 2, ans = 0;
        while(x < res.size() - 1) {
            while(y <= res.size() - 1 && res[y] - res[x] < k) ++y;
            if(y <= res.size() - 1 && res[y] - res[x] == k) ans++;
            x++;
            if(x == y) y++;
        }
        cout << ans;
    }

-2

kietjumper đã bình luận lúc 25, Tháng 7, 2025, 15:15 ← sửa 3 →

Bài này ta for từ 1->n-k, nếu i và i+k đồng thời là snt thì cnt++.