題目

讓我們定義$d_{n}$​ 爲：$d​_{n}​ =p_{​n+1}​​ −p_{​n}$​​ ，其中$p_{​i}$是第i個素數。顯然有$d_{1}=1$，且對於$n>1$有$d​_n$是偶數。「素數對猜想」認爲「存在無窮多對相鄰且差爲2的素數」。現給定任意正整數$N(<10^5​​)$，請計算不超過$N$的滿足猜想的素數對的個數。

輸入格式

輸入在一行給出正整數N。

輸出格式

在一行中輸出不超過N的滿足猜想的素數對的個數。

輸入樣例

20

輸出樣例

4

程式碼

#include <stdio.h>
#include <math.h>
#include <malloc.h>

#define true 1
#define false 0

typedef struct list{
    int *a;
    size_t length; //線性表長度
    size_t size; //線性表大小
} list;

//線性表初始化
void init(list * list){
    list->a = (int *) malloc(sizeof(int)*10);
    if(!list->a)
        exit(-1);
    list->length = 0;
    list->size = 10;
}

//線性表擴充套件
void expand(list * list){
    list->a = (int *) realloc(list->a, sizeof(int)*(list->size+10));
    if(!list->a)
        exit(-1);
    list->size += 10;
}

//在尾部插入元素，時間複雜度o(1)
void push(list * list, int n){
    if(list->length == list->size-1)
        expand(list);
    list->a[list->length] = n;
    list->length++;
}

//素數判定，時間複雜度o(√n)，判定素數只需要檢測√n個元素即可
_Bool isprime(int n){
    int k;
    k = (int)sqrt((double)n);
    _Bool result = true;
    for(int i = 2; i <= k; i++){
        if(n%i == 0){
            result = false;
            break;
        }
    }
    return result;
}

int main(void){
    int n, count = 0;
    list list;
    scanf("%d",&n);
    init(&list);
    push(&list, 2);
    for(int i = 3; i <= n ; i+=2){
        if(isprime(i))
            push(&list, i);
    }
    for(int i = 1; i <= list.length; i++){
        if(list.a[i] - list.a[i-1]==2)
            count++;
    }
    printf("%d\n",count);
    return 0;
}

小結

本題主要是對素數的一個判定，判定並不需要檢測$n-1$個元素，只需要檢測是否能被$\sqrt{n}$個元素整除即可。使用線性表是爲了更好的管理記憶體，即將元素儲存進線性表中。事實上，由於素數肯定是從小到大遞增的，可以直接在遍歷3~n的過程中計算$d_i$，並進行統計。