c - 寻找最接近的质数

Question

这不是一个容易问的问题。 我正在编写一个代码，它会询问“n”。然后要求n个数字，最后打印与其中一个最接近的素数有多远。 问题是编译时间应该少于 4 秒，而我无法在 5 秒内得到它。

 #include <stdio.h>
int f (int n){
    int i;
    int a;
    int b;
    int dif=0;
    for ( i = 2 ; i<n ; i++) 
        if (n%i == 0)
            return 0;
    if (n == 0 || n == 1)
        return 0; 
    return 1;

}
int main (){
    int dif=0;
    int difall=10000;
    int a;
    int b;
    int input;
    long long input2;
    scanf("%d",&input);
    int i;
    for (i == 1;i<input;i++){
        scanf("%d",&input2);
        dif=0;
        while (1==1){
        a=input2+dif;
        b=input2-dif;
        if (f(a) == 1 && a>=0){
            if (dif<difall)
                difall=dif;
            break;}
        if (f(b) == 1 && b>=0){
            if (dif<difall)
                difall=dif;
            break;}
        dif++;

    }
    }
    printf("%d",difall);
}

Answer 1

The problem is the compile¹ time should be less than 4 secs and I can't get it under 5 s.

测试素数有许多潜在的优化。

OP 当前迭代 [2...n)

// slow
for ( i = 2 ; i<n ; i++) 
        if (n%i == 0)
            return 0;

仅需要 [2...sqrt(n)]。

// faster
for ( i = 2; i <= n/i; i++) {
  if (n%i == 0) {
    return 0;
  }
}

可能存在其他问题，但上述问题会加快代码速度。

<小时/>

¹ 当然，运行时间是这里的问题。