讓我們定義 dn 為：dn = pn+1 - pn，其中 pi 是第i個素數(shù)蚌卤。顯然有 d1=1 且對于n>1有 dn 是偶數(shù)意荤⊙滔冢“素數(shù)對猜想”認為“存在無窮多對相鄰且差為2的素數(shù)”。
現(xiàn)給定任意正整數(shù)N (< 10?)康辑，請計算不超過N的滿足猜想的素數(shù)對的個數(shù)对省。
輸入格式：每個測試輸入包含1個測試用例蝗拿，給出正整數(shù)N。
輸出格式：每個測試用例的輸出占一行蒿涎，不超過N的滿足猜想的素數(shù)對的個數(shù)哀托。
輸入樣例：
20
輸出樣例：
4
思路：創(chuàng)建一個10000的數(shù)組， 查找 0~N 的素數(shù)并存儲到數(shù)組中劳秋， 然后在數(shù)組中查找素數(shù)對仓手，并記錄個數(shù)；
C語言：
#include <stdio.h>
int is_prime(int n);
const int N = 100000;
int main(void)
{
int prime[N];
int count = 0;
int n, flag;
scanf("%d", &n);
// 找素數(shù)
int i;
for (i=2; i<=n; i++){
if (is_prime(i)){
prime[count++] = i;
//printf("%d\n", i);
}
}
// 查找素數(shù)對對數(shù)
int sum = 0;
for (i=0; i<count-1; i++){
if (prime[i+1] - prime[i] == 2){
sum++;
}
}
printf("%d", sum);
return 0;
}
// 判斷 n 是否為素數(shù)
int is_prime(int n)
{
int j;
int flag = 1;
for (j=2; j<n/2+1; j++){
if (n%j == 0){
flag = 0;
break;
}
}
return flag;
}
最后一個測試沒有通過玻淑，超時了嗽冒，看來要優(yōu)化算法。
1107.jpg
用另一種方法重寫了：
#include <stdio.h>
int main(void)
{
int n;
scanf("%d", &n);
int arr[n+1];
// 初始化為 1
int i, j;
for (i=2; i<n+1; i++){
arr[i] = 1;
}
// 將質(zhì)數(shù)的倍數(shù)標記為非質(zhì)素
for (i=2; i<n+1; i++){
if (arr[i] == 1){
for (j=2; i*j <= n; j++){
arr[i*j] = 0;
}
}
}
int count = 0;
int temp = 2; // 記錄當前素數(shù)补履，前面的那位素數(shù)添坊。
int num;
for (i=3; i<n+1; i++){
if (arr[i] == 1){
if (i - temp == 2){
count++;
}
temp = i;
}
}
printf("%d", count);
return 0;
}
構(gòu)造素數(shù)表.jpg
