Проект Эйлера № 3, бесконечный цикл по факторизации

Question

Итак, я занимаюсь Project Euler, потому что, дорогие боги, мне нужно попрактиковаться в написании кода, а также мои математические навыки ржавые, как что-то очень ржавое. Thusly; Проект Эйлера. Я уверен, что большинство здесь уже видели или слышали о проблеме, но я поставлю ее здесь только для полноты:

Основными факторами 13195 являются 5, 7, 13 и 29. Что является самым большим основным фактором числа 600851475143?

Для этого я написал две функции:

from math import sqrt

def isprime(n):
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    for x in range(3, round(sqrt(n))+1, 2):
        if n % x == 0:
            return False
    else:
        return True

Это просто проверяет любой номер подачи на простоту. Он работает как задумано (насколько я знаю), но теперь, когда я сказал, что я расту неуверенно. В любом случае, он сначала проверяет особые случаи: 1 (не простое), 2 (простое) или делится на 2 (не простое). Если ни один из особых случаев не происходит, выполняется общий тест на простоту.

Это мой код факторизации:

def factorization(n):
   factor = 2
   x = 3
   while True:
       if n % x == 0:
           if isprime(x):
               factor = x
               n = n // x
               if n == 1:
                   return factor
           else:
               return factor
       x += 2

И это определенно не работает, как задумано. К сожалению, он работает на конкретное значение проблемы Project Euler, но не работает, скажем, на 100. Я не уверен, что мне нужно сделать, чтобы это исправить: что происходит, если это число типа 100, он правильно найдет первые 5 (2 * 2 * 5), но после этого будет зацикливаться и устанавливать x = 7, что сделает весь цикл бесконечным, потому что ответ 2 * 2 * 5 * 5. Поможет ли здесь рекурсия? Я попробовал это, но это не получилось более симпатичным (это все еще пошло бы в бесконечный цикл для некоторых чисел). Я не уверен, как решить это сейчас.

Answer 1

Вы на правильном пути, но вам необходимо учитывать возможность повторения факторов.Вы можете сделать это примерно так:

factors = []

while num % 2 == 0:
  factors.append(2)
  num /= 2

Идея в том, что вы будете продолжать добавлять 2 в список факторов, пока число, которое вы тестируете, не станет нечетным.Вы можете использовать аналогичную логику и для других факторов, чтобы улучшить метод факторизации.

Answer 2

Я думаю, что вы сделали проблему более сложной, чем необходимо

Вот некоторый псевдокод, который вы сможете превратить в код Python

from itertools import count
n=600851475143  
for x in count(2):
    while x divides n:
        divide n by x
    if n==1:
        print x # largest factor will be the last one
        break

Answer 3

Вот еще одно оптимизированное решение:

import math

def find_prime(num):
    if num <= 1:
        return False
    elif(num == 2):
        return True
    elif( num % 2 == 0):
        return False
    for i in range(3, int(math.sqrt(num))+1, 2): 
        if num%i == 0:
            return False 
    return True

def prime_factor(number):
    pf = number;
    divList = [];

    for i in range(2, int(math.sqrt(number))):
        if number % i == 0 :
            divList.append(i)

    for n in divList:
        if(find_prime(n)):
            pf = n;

    return pf

num = 600851475143
print("Max prime factor :", prime_factor(num))

Answer 4

Для повторяющихся (нечетных) факторов просто увеличьте x, если делитель не найден:

def factorization(n):
    factor = 2
    x = 3
    while True:
        if n % x == 0:
            if isprime(x):
                factor = x
                n = n // x
                if n == 1:
                    return factor
            else:
                return factor
        else:
            x += 2

OTOS, кажется, что вы всегда упускаете "2" факторов. Наклейте их сверху, а затем сделайте основной цикл

РЕДАКТИРОВАТЬ (после комментария)

Вы можете сделать намного проще:

def factorization(n):
    factors = []
    x = 2
    while True:
        while n % x == 0:
            factors.push(x)
            n /= x
        if n == 1:
            return factors
        if x == 2:
            x = 3
        else: 
            x += 2