PAT 乙级 1007 运行超时 该如何改进

Question

输入和输出都没有问题，但当我输入10^5^时显示超时
我想问一下是哪部分的代码导致了运行时间超时呢？
该如何改进呢？

#include <stdio.h>
int main(void){  //超时
    int n;
    int cnt = 0;
    int p1=2, p2;
    int k = 0;

    scanf("%d", &n);
    int a[n];
    
    int i, j;
    for( i=2; i<=n; i++){  //只能从2开始 因为1%2==1 但1不是素数
        int isPrime = 1;
        for( j=2; j<i; j++){
            if(i%j==0){
                isPrime =0;
                break;
            }
        }     
        
        if( isPrime == 1){
            p2 = i;
            if(p2-p1==2){
                cnt++;
            }
            p1 = i;
        }
        
    }
    printf("%d", cnt);

    return 0;
}

Answer 1

你的需求是什么呢？是求小于指定的整数间有多少个素数吗？
for( j=2; j<i; j++){ 这个循环效率低了
改为：
for( j=2; j*j<=i; j++){