Застрял в режиме работы ноутбука Jupyter

Question

Мой ноутбук Jupyter застревает в режиме запуска всякий раз, когда я запускаю оболочку со следующим кодом:

def is_prime(num):
    if num < 2:
        return False  
    for x in range(2, num - 1):
        if num % x == 0:
            return False  
    return True  

prime_list = []    
num = 2

while True:    
    if is_prime(num):
        prime_list.append(num)
    num += 1
if len(prime_list) == 10002:
    break


print(prime_list[-1])    

Может кто-нибудь запустить этот код на своем компьютере и сказать мне, что вывод? Буду очень признателен за любой ответ.

Answer 1

Ваш код застревает, потому что ваша основная функция тестирования становится очень медленной!

Я выполнил ваш код с различными остановочными точками: 100, 1000, 2000 и 4000 простых чисел. Запуски заняли 0,01, 0,23, 0,98 и 4,31 секунды соответственно.

Вы можете видеть, что удвоение числа простых чисел, чтобы найти (примерно), в четыре раза больше времени. Это имеет смысл, учитывая, что для проверки, является ли n простым, вы должны проверить его по n-2 другим числам (исключая 1 и n). Итак, ваш алгоритм имеет сложность времени , по крайней мере, O(n^2), чтобы найти n простых чисел.

(также я получил 104759 после того, как 10002 простых числа были найдены через 30 секунд. Сначала я случайно набрал «100002», что длилось довольно долгое время без каких-либо результатов ... )