Как ускорить код?

Question

[Владислава]

Как можно ускорить данный код хоть немного?

import random
def is_prime(num):
    k = num-1
    if k == 2 or k<1 or k<3:
        a = 2
    else:
        a = random.randint(2, k)
        
    if num>1 and num != 6:
        if a**num % num == a % num:
            return True
        else:
            return False
    else:
        return False

Comments

[Vindicar]

А что он пытается сделать вообще?

Answer 1

[galaxy]

Давайте так: что вообще этот код делает?
Похоже на тест простоты Ферма, но реализация ошибочная. Да и сам тест вероятностный, т.е. может дать false positive результат.

Если уж сильно хочется именно этот кусок непонятно чего оптимизировать, то, очевидно, что для больших чисел num возведение в степень a**num будет очень медленным. В питоне есть функция pow, которая имеет волшебный третий параметр и умеет вычислять возведение в степень по модулю очень быстро.

Comments

[Владислава]

Код написан для задачки с codewars. Я действительно взяла идею теста Ферма. Данный код прошел все встроенные тесты. Но при прохождении рандомных тестов выкидывает что по времени не прохожу.
А за функцию pow спасибо)

[galaxy]

Владислава, вот я потестировал ваш код, смотрите:

>>> is_prime(13)
True
>>> is_prime(13)
True
>>> is_prime(15)
True
>>> is_prime(15)
True
>>> is_prime(15)
True
>>> is_prime(15)
False
>>> is_prime(15)
False

Тест простоты Ферма - нестрогий. Возьмите лучше код из Википедии, например

[Владислава]

galaxy, спасибо!