Блог

Главная - Вопросы по программированию - Как мне ускорить выполнение этого кода на C при определении того, является ли большое число простым числом или нет?

Как мне ускорить выполнение этого кода на C при определении того, является ли большое число простым числом или нет?

#c #performance #primes

#c #Производительность #простые числа

Вопрос:

 #include <stdio.h>
#include <math.h>

bool isPrime(long long int n) {
    if(n <= 1) {
        return false;
    } else {
        for(long long int i = 2; i <= sqrt(n); i  ) {
            if(n % i == 0) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    
    int cases;
    long long int num;
    scanf("%d", amp;cases);
    
    for(int i = 0; i < cases; i  ) {
        scanf("%lld", amp;num);
        if(isPrime(num)) {
            printf("YESn");
        } else {
            printf("NOn");
        }
    }
    
    return 0;
}

Могу ли я каким-либо образом ускорить выполнение этого кода? Я попробовал алгоритм сита Эратосфена, но он был медленнее, и, по-видимому, это «попытка разделить число от 2 до его квадратного корня» быстрее, но недостаточно быстро, по мнению онлайн-судьи.

Комментарии:

1. Вы вызываете sqrt() функцию для каждого цикла, вы можете просто вызвать ее один раз, сохранить результат в виде целого числа и сравнить его с этим целым числом. Вы включаете оптимизацию компилятора?

2. Вы можете сделать это в два раза быстрее, начав с 3 и увеличив на два (вы должны обрабатывать %2 вне цикла).

3. Насколько большим будет cases и num будет? Когда num простое число близко 10**18 , цикл будет выполняться 10**9 несколько раз, и это будет слишком много для типичной онлайн-системы оценки. Я предполагаю, что вам следует использовать алгоритм сита Эратосфена, потому что вам приходится обрабатывать несколько запросов.

4. Самое основное улучшение действительно заключается в проверке только нечетных чисел. Вы можете проверить тысячи других сообщений о простых числах, представленных на SO, для вдохновения.

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