Время выполнения простого алгоритма поиска в Python - PullRequest
Новая
       26

Время выполнения простого алгоритма поиска в Python

1 голос
/ 06 марта 2019

Проблема:

У меня есть следующая задача:

[...] написать программу, которая получает положительное целое число больше 1 и проверяет, является ли оно простым или составным.

Решение:

Я придумал следующее: 

n=int(input())
flag=True
for i in range(2,n//2+2):
    if n%i==0:
        print("Not prime.")
        flag=False
        break
if flag==True:
    print("Prime.")

Что казалось правильным. Затем я решил поиграть с ним и посмотреть, как все будет работать с большим целочисленным вводом, и 10 ^ 9 + 7 выглядело как хороший выбор. Однако программа, похоже, вообще не заканчивала работу и продолжала работать более 30 секунд, пока я не решил ее убить.

Но, учитывая, что цикл в алгоритме выполняется не более ~ 5 * 10 ^ 8 раз, и учитывая огромное количество вычислений, которые современный компьютер может выполнить за секунду, не слишком ли долго это время выполнения?

Что здесь происходит?

Работает ли 10 ^ 9 + 7 как «верхняя граница» для вычислений типа int в Python, так же как и в C, таким образом «переполняя вычисления» каким-то образом? Или что-то не так с моим алгоритмом?

Заранее спасибо!

1 Ответ

0 голосов
/ 06 марта 2019

Конечно, в интерпретируемом языке, таком как Python, дела идут медленнее - иногда вы можете потерять один или два порядка производительности по сравнению с эквивалентной реализацией Си. Однако ваш алгоритм асимптотически намного хуже, чем необходимо. Ваш алгоритм O(n), но, проверяя делимость только до квадратного корня из n, вы можете достичь O(sqrt(n)) времени. Вы также можете ускорить это за счет некоторых постоянных факторов, применяя факторизацию колес. Колеса {2, 3} и {2, 3, 5} довольно распространены, но вы получаете убывающую отдачу, когда добавляете больше простых чисел к колесу. Для простоты использования колеса {2} мы можем пропустить все четные числа (кроме 2), поскольку ни одно из них не будет простым. 

def is_prime(n):
    if n < 3:
        return n == 2
    if not n % 2:
        return False

    for i in range(3, int(n ** 0.5) + 2, 2):
        if not n % i:
            return False
    return True
...