PTA 中国大学MOOC-陈越、何钦铭-数据结构-起步能力自测题

时间复杂度为O(n^2)，判断素数只用判断到sqrt(n)这样可以把运行时间缩短好几倍

#include <stdio.h>
#include <math.h>
int isPrime(int num);
int main(void){
    int n,i,counter;
    scanf("%d",&n);
    int a[n];
    //给a[]初始化
    for(i=0;i<n;i++){
        a[i] = 0;
    }
    for (i=2;i<n+1;i++){
        if(isPrime(i)) a[i-1]=1;
    }
    counter=0;
    for(i=2;i<n;i++){
        if(a[i]&&a[i-2]) counter+=1;
    }
    printf("%d\n",counter);
}
//用来判断是不是质数
int isPrime(int num){
    int i,r;
    r=1;
    for(i=2;i<=sqrt(num);i++){
        if(num%i==0) {
            r = 0;
            break;
            }
    }
    return r;
}