поиск ближайшего простого числа

Question

Это не простой вопрос. Я пишу код, который будет спрашивать «п». Затем попросите 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

Проблема в том, что время компиляции ¹ должно быть меньше 4 секунд, и я не могу получить его менее чем за 5 секунд.

Есть много потенциальных оптимизаций для тестирования простоты.

В настоящее время 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;
  }
}

Могут существовать другие проблемы, но приведенные выше будут ускорять код.

---

¹ Конечно, проблема времени выполнения здесь.