Как ускорить процесс поиска?

Question

Я занимался проблемой 7 в Project Euler, когда у меня возникла проблема. Мой код длился долго. Вот мой код.

def Problem7(): 
    num = 0 
    p = 0 
    while p < 10002 : 
     prime = True 
     for i in range(2,num): 
      if (num%i==0): 
       prime = False 
     if prime: 
      print(num) 
      p = p + 1 
     num = num + 1 
Problem7() 

Как это сделать быстрее? Есть ли другой способ?

Answer 1

Вы должны сделать свою жизнь проще и распечатать счетчик посещений в конце, что я подозреваю, что переменная p хранит.

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

1: Проверьте, если число четное (NUM% 2) (если да, то не простое)

2: В то время как делитель меньше или равен квадратному корню и загрунтовать == Правда, тест делителей

3: Если еще не простой, прирост на 2, так что вы только проверить нечетные числа (Все эвены были проверены с NUM% 2)

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

Если вы думаете о номере 100, ваша логика проверяет 99 возможных делителей. Вышеуказанные логические тесты только 2 останавливаются. Худший случай перехода к квадратному корню будет только 2,3,5,7,9 ... 5 расчетов вместо 99.

Answer 2

Я использовал следующий метод, чтобы проверить, является ли число простым (работает в 0m0.612s):

import math 

def is_prime(num): 
    if num == 0 or num == 1: 
     return False 
    if num == 2: 
     return True 
    temp = 2 
    while temp < math.sqrt(num) + 1: 
     if num % temp == 0: 
      return False 
     temp += 1 

    return True