Блог

У меня есть две функции: isPrime и alsoPrime . Оба предназначены для возврата True или False, если число (x) является простым числом. isPrime(x, pLis) берет растущий список чисел простых чисел и смотрит, кратно ли x каким-либо простым числам. alsoPrime(x) выполняет поиск по всем нечетным числам, начинающимся с 3 и заканчивающимся корнем из x. Затем я использую цикл for, начинающийся с 3 и увеличивающийся с интервалом в 2.

Я ожидал, что isPrime будет быстрее, потому что он должен пропускать числа, т.е.:

Первичный -> 3, 5, 7, 11, 13, 17, 19

alsoPrime -> 3, 5, 7, 9, 11, 13, 15, 17, 19

Но alsoPrime это намного быстрее — в 100 раз быстрее при поиске по первым 1 000 000 номерам.

Может кто-нибудь, пожалуйста, объяснить, почему? Требуется ли много времени, чтобы звонить pLis каждый раз?

 
def isPrime(x, pLis):
    for item in pLis:
        if x % item == 0:
            return False
    return True


def alsoPrime(x):
    for i in range(3, round(x**0.5) 1, 2):
        if x % i == 0:
            return False
    return True

 

Вы просматриваете все простые числа, которые вы обнаружили, isPrime когда вам действительно нужно только перейти к квадрату кандидата, как вы это делаете alsoPrime . Больше итераций означает более медленный код. Еще один быстрый способ проверить это — подсчитать количество итераций, например:

 def isPrime(x, pLis):
    for i, item in enumerate(pLis):
        if x % item == 0:
            print(f"{x} is not prime after {i} iterations")
            return False
    print(f"{x} is prime after {i} iterations")
    return True