Hãy xác định số lượng số nguyên tố p thỏa mãn điều kiện n < p < 2n Định đề Bertran: “ Với mọi số nguyên n ≥ 2 bao giờ cũng tìm thấy số nguyên tố p thỏa mãn n < p < 2n”. Định đề này do nhà toán học Pháp Jojeph Bertran đưa ra năm 1845 sau khi đã kiểm tra với mọi n ≤ 3 000 000. Điều này đã được Tchebưsep chứng minh năm 1850. Năm 1932 Erdoeus đã tìm được cách chứng minh mới đơn giản hơn. Nhiệm vụ của bạn rộng hơn một chút: với n cho trước, hãy xác định số lượng số nguyên tố p thỏa mãn điều kiện n < p < 2n. INPUT gồm nhiều tests, mỗi test cho trên một dòng chứa số nguyên dương n (1 ≤ n ≤ 10^7). OUTPUT kết quả mỗi test đưa ra trên một dòng dưới dạng một số nguyên. Code theo C++

1 câu trả lời

code C++

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

const int MAXN=3000000+5;

int n;

bool prime[MAXN*2];

void khoitao()

{

memset(prime,true,sizeof(prime));

for(int i=2;i*i<2*MAXN;i++) if (prime[i])

for(int j=2;i*j<2*MAXN;j++)
prime[i*j]=false;

return;

}

int main()

{

freopen("BERTRAN.INP","r",stdin);

freopen("BERTRAN.OUT","w",stdout);

khoitao();

while (cin>>n) {

int ans=0;

for(int i=n+1;i<2*n;i++) ans+=(int)prime[i];

cout<<ans<<'\n';

}

return 0;

}