1007补

//1007 素数对猜想（20 分）
//让我们定义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

C:

#include <stdio.h>
#include <math.h>
int main(int argc, const char * argv[])
{
    
    int N;//正整数N
    scanf("%d", &N);
    int prime[100000] = {2,3};//2,3是素数但不是猜想素数对，为方便，进行这样初始化，事实上数组大小不需要这么大。
    int paircnt = 0;//素数对个数，当前是2,3，素数对个数为0
    int current = 1;//标记，当current==1时表示是素数，current==0时非素数
    int primecnt = 2;//为了方便对素数数组的添加设定的索引
    for (int i = 4; i <= N; i++) {//从4开始到N找其中的素数
        current = 1;//每次循环标记初始化为1
//        for (int j = 2; j <= sqrt(i); j++) {//从2开始，只要判断“2~根号i”间的素数不能被当前数整除，则为素数
        for (int j = 0; prime[j] <= sqrt(i); j++) {
//            if (i % j == 0) {//整除，非素数
            if (i % prime[j] == 0) {
                current = 0;//标记为0
                break;//只要有一个j使i为非素数，就可以跳出循环了
            }
        }
            if (current == 1) {//如果标记为1，即当前数为素数的话
                prime[primecnt] = i;//放入素数数组
                primecnt++;//数组索引+1
            }
    }
//    for (int i = 0; i < primecnt; i++) {      //这段注释用于验证上述程序是否正确
//        printf("%d ",prime[i]);
//    }
    for (int i = 0; i < primecnt; i++) {
        if(prime[i+1] - prime[i] == 2)  paircnt++;  //这里要注意后面减前面，因为数组是0开始的
    }
            printf("%d\n",paircnt);
    return 0;
}

与之前1007相比，此方案只需要把当前数和之前的素数相余。这样循环次数可以减少很多。这是我在做1013时看OliverLew的思路才明白的。