找到最接近的素数

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;
  }
}

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

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

找到最接近的素数

finding closest prime number

c

primes

compile-time