Question

Câu 2 (5.0 điểm): Tổng nguyên tố                                                  SPRIME.PAS

Một số tự nhiên n có thể phân tích được dưới dạng tổng của hai số nguyên tố.

Ví dụ: Số 8 có một cách phân tích thành tổng hai số nguyên tố là 3 và 5; Số 11 không có cách phân tích nào thành tổng của hai số nguyên tố.

Yêu cầu: Cho số nguyên dương n, hãy đếm số cách phân tích n thành tổng của hai số nguyên tố.

Dữ liệu vào: Cho trong file văn bản SPRIME.INP có cấu trúc như sau:

- Dòng 1: Ghi số nguyên dương n ( 1≤  n ≤ 10000).

Dữ liệu ra: Ghi ra file văn bản SPRIME.OUT theo cấu trúc như sau:

- Dòng 1: Ghi số nguyên đếm được.

Ví dụ:

SPRIME.INP	SPRIME.OUT
30	3

 

Giải thích:  Trong ví dụ trên số 30 có 3 cách phân tích thành tổng của hai số nguyên tố như sau: 30 = 7 + 23; 30 = 11 + 19 và 30 = 13 + 17.

pascal nha help mik vs a

 

Answer 1

#include <bits/stdc++.h>
using namespace std;
#define nmax 10000005
bool NT[nmax];
void sang()
{
    memset(NT, true, nmax);
    NT[0]=NT[1]=false;
    for (int i=2; i<=sqrt(nmax); i++)
        if (NT[i])
            for (int j=i*i; j<=nmax; j+=i)
                NT[j]=false;
}
int main()
{
    freopen("SPRIME.inp", "r", stdin);
    freopen("SPRIME.out", "w", stdout);
    long long n;
    cin>>n;
    sang();
    long long dem=0;
    for(int i=1; i<=n/2; i++)
    {
        if(NT[i] and NT[n-i]) dem++;
    }
    cout<<dem;
}