孿生素數問題 時間限制：3000 ms | 內存限制：65535 KB 難度：3 描述 寫一個程序，找出給出素數范圍內的所有孿生素數的組數。一般來說，孿生素數就是指兩個素數距離為2，近的不能再近的相鄰素數。有些童鞋一看到題就開始寫程序，不仔細看題，咱們為了遏制一下讀題不認真仔細的童鞋，規定，兩個素數相鄰為1的也成為孿生素數。 輸入 第一行給出N(0<N<100)表示測試數據組數。 接下來組測試數據給出m，表示找出m之前的所有孿生素數。 (0<m<1000000) 輸出 每組測試數據輸出占一行，該行為m范圍內所有孿生素數組數。 樣例輸入 1 14樣例輸出 4 [cpp] /********************************* * 日期：2013-3-14 * 作者：SJF0115 * 題號: 南陽理工 題目26: 孿生素數問題 * 來源：http://acm.nyist.net/JudgeOnline/problem.php?pid=26 * 結果：AC * 來源： * 總結： **********************************/ #include<stdio.h> #include<math.h> int prime[1000001]; //素數表 int Primes(int n){ int i,j; for(i = 1;i <= n;i++){ //偶數 if(i % 2 == 0){ prime[i] = 0; } //奇數 else{ prime[i] = 1; } } //奇數的倍數肯定不是素數 for(i = 3;i <= sqrt(n);i+=2){ if(prime[i]){ for(j = i+i;j <= n;j += i){ prime[j] = 0; } } } return 0; } int main(){ int N,M,count,i; while(scanf("%d",&N) != EOF){ while(N--){ count = 0; scanf("%d",&M); //求素書 Primes(M); //求孿生素數 for(i = 2;i <= M-2;i++){ if(prime[i] && prime[i+2]){ count++; //printf("%d %d\n",i,i+2); } } //兩個素數相鄰為1的也成為孿生素數。這樣的只有一種情況2,3 if(M >= 3){ count++; } printf("%d\n",count); } } return 0; } /********************************* * 日期：2013-3-14 * 作者：SJF0115 * 題號: 南陽理工 題目26: 孿生素數問題 * 來源：http://acm.nyist.net/JudgeOnline/problem.php?pid=26 * 結果：AC * 來源： * 總結： **********************************/ #include<stdio.h> #include<math.h> int prime[1000001]; //素數表 int Primes(int n){ int i,j; for(i = 1;i <= n;i++){ //偶數 if(i % 2 == 0){ prime[i] = 0; } //奇數 else{ prime[i] = 1; } } //奇數的倍數肯定不是素數 for(i = 3;i <= sqrt(n);i+=2){ if(prime[i]){ for(j = i+i;j <= n;j += i){ prime[j] = 0; } } } return 0; } int main(){ int N,M,count,i; while(scanf("%d",&N) != EOF){ while(N--){ count = 0; scanf("%d",&M); //求素書 Primes(M); //求孿生素數 for(i = 2;i <= M-2;i++){ if(prime[i] && prime[i+2]){ count++; //printf("%d %d\n",i,i+2); } } //兩個素數相鄰為1的也成為孿生素數。這樣的只有一種情況2,3 if(M >= 3){ count++; } printf("%d\n",count); } } return 0; } 注意： 接下來組測試數據給出m，表示找出m之前的所有孿生素數。 但實際上包括m這個數。 測試用例： m = 7 孿生素數： 2,3 3,5 5,7
