pat B級1007素数対推定(20点)
d nは、d n=p n+1−p nであり、p iはi番目の素数であると定義する.明らかにd 1=1であり、n>1ではd nが偶数である.「素数対推測」は「隣接して差が2の素数が無限に多い」と考えられる.任意の正の整数N(<10 5)を与え、Nを超えない推定素数対を満たす個数を計算してください.入力形式:1行に正の整数Nを入力します.出力フォーマット:1行にNを超えない予想を満たす素数対の個数を出力する.入力サンプル:20
出力サンプル:4
出力サンプル:4
// cin>>n; int p[n]; , cin>>n; int p[n]={0}; !!!(cin>>n; int p[1000]={0}; )// n , [2,sqrt(n)]
#include
#include
using namespace std;
int main(){
int n=0;
cin>>n;
int p[n];// ,
int m=2,i=0;
if(n<5)
cout<<0;
else{
while((m)<=(n)) {
int k=2;
while((m)%(k)!=0) {
if(k>(int)sqrt(m)) {
p[i++]=m;
break; }
k++; }
m++; }
i=0;m=0;
while(p[(i)+1]) {
if(p[i+1]-p[i]==2) m+=1;
i++;}cout<<m;
}
return 0;
}