pat B級1007素数対推定(20点)

6045 ワード

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
//    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;
 }