Phân tích thành tổng hai số nguyên tố - LCOJ: Luyện Code Online Judge

NGTO - Phân tích thành tổng hai số nguyên tố

Điểm: 1,00 (OI)

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

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 một số nguyên dương ~n~. Bạn hãy đếm số cách phân tích số ~n~ thành tổng hai số nguyên tố khác nhau ~u,v\ (u< v)~.

Input

Số nguyên dương ~n\ (2≤n≤3×10^5)~.

Output

Dòng đầu ghi một số nguyên ~k~ là số cách phân tích thỏa mãn điều kiện đề bài. Nếu không có cách phân tích ghi số ~0~.
Trường hợp ~k>0, k~ dòng tiếp theo, dòng thứ ~i~ ghi hai số ~u_i,v_i\ (u_i< v_i)~ là cách phân tích thứ ~i~ theo yêu cầu: ~u_1< u_2<…< u_k~.

Sample

Input #1

Output #1

Input #2

Output #2

Hint

Số ~82~ có ~4~ cách phân tích ~82=3+79=11+71=23+59=29+53~. Cách phân tích ~82=41+41~ không được tính vì ~u=v~.
Số ~11~ không phân tích được.

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

Bình luận

Please read the guidelines before commenting.

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 3e5 + 1;
bool p[MAXN];
int n;
int dd[MAXN], a[MAXN], b[MAXN];
int v = 0;
int k = 0;

void sieve(){
    fill(p, p + MAXN, true);
    p[0] = p[1] = false;
    for (int i = 2; i * i <= MAXN; i++){
        if (p[i]){
            for (int j = i * i; j <= MAXN; j += i){
                p[j] = false;
            }
        }
    }
}

int main(){
    cin.tie(0)->ios_base::sync_with_stdio(0);
    sieve();
    cin >> n;
    for (int i = 0; i <= n; i++){
        if (p[i]){
            dd[v++] = i;
        }
    }

    int i = 0, j = v - 1;
    int res = 0;

    while (i < j){
        if (dd[i] + dd[j] > n){
            j--;
        }
        else if (dd[i] + dd[j] < n){
            i++;
        }
        else{
            res++;
            a[k] = dd[i++];
            b[k] = dd[j--];
            k++;
        }
    }

    cout << res << '\n';
    for (int i = 0; i < k; i++){
        cout << a[i] << " " << b[i] << '\n';
    }
}

-1

ntm_mtn đã bình luận lúc 25, Tháng 10, 2023, 16:32

ad ơi cho e xin editorial bài này đc ko ạ

0

Docladongnai đã bình luận lúc 1, Tháng 8, 2024, 14:33

sử dụng công thức vét cạn cx được bạn ạ