Prime программа факторизация в питоне не дает выхода

Question

Я работаю над проектом по Euler задаче 3,

простые множители 13195 являются 5, 7, 13 и 29.What является крупнейшим основным фактором числа 600851475143?

Код, который я придумал следующим образом:

def q_prime(a): 
    if a == 2: 
      return True 
    elif a < 2: 
      return False 

    for i in range(2,a): 


      if a%i == 0: 
        return False 
    else: 
      return True 


def prime_factor(x): 
    prime_factors =[] 
    for i in range(1,x): 
      if q_prime(i) == True and x%i == 0: 
        prime_factors.append(i) 
    return prime_factors 

Вызов этой функции 13195 дал мне [5,7,13,29], как и ожидалось. Я пробовал некоторые другие комбинации, такие как 1035, которые дают [3,5,23]. Однако, когда я вызываю эту функцию на 600851475143, я не получаю никакого вывода. Более того, я тоже не получаю сообщение об ошибке. Он работает некоторое время, и простой перезапуск оболочки

Я знаю, что это не элегантный код, и я догадываюсь, что грубый заставляет меня преодолеть такую ​​проблему, потому что большое количество вызывает эту проблему? Что именно происходит?

Answer 1

Вот что происходит, когда я пытаюсь запустить свой код, используя Python 2.7:

$ python primes.py 
Killed: 9 

Вопрос заключается в том, что range(2, 600851475143) пытается создать список 600851475141 элементов. Это слишком велико, чтобы вписаться в память вашего компьютера, поэтому программа Python будет убита.

Вы можете попробовать заменить range() на xrange(), но ваша программа займет слишком много времени. Вам нужен лучший алгоритм.

P.S. В вашем коде также есть ошибка, что означает, что он не работает для простых входов.

Answer 2

Номер 600851475143 является слишком большим. Вы можете упростить вычисления, если в q_prime и в prime_factor вы проверите номер не в диапазоне [2, n] bun в диапазоне [2, sqrt (n) +1]. Это также вернет правильный результат, но займет меньше времени:

import math 

def q_prime(a): 
    if a == 2: 
      return True 
    elif a < 2: 
      return False 

    for i in range(2, int(math.sqrt(a) + 1)): 
      if a%i == 0: 
       return False 
    else: 
     return True 


def prime_factor(x): 
    prime_factors =[] 
    for i in range(1, int(math.sqrt(x) + 1)): 
      if q_prime(i) == True and x%i == 0: 
        prime_factors.append(i) 
    return prime_factors 

Answer 3

Обе функции, которые вы написали, проблематичны, учитывая размер проблемы. q_prime(a) Петли до a и prime_factor(x) петель до x, вызывающих q_prime на каждой итерации. Это делает ваш алгоритм O(N^2), что слишком много для числа, такого как 600851475143.

лучше подход (O (√N) -> по существу, непосредственный результат):

• функционального генератор с использованием sieve of Eratosthenes с получением простых чисел
• цикла через простые числа до sqrt(n) сбора факторов, в то время как сокращается n с каждым фактором найдены
  • добавить n себя, если нет других факторов, где найдены