Поиск наибольшего простого множителя заданного числа в Python

Это проблема проекта Эйлера. Какой самый большой простой делитель числа 600851475143? Я написал следующий код:

def prime_factors(x):
    my_list = []
    for no3 in range(2, int(x)):
        i = 0
        if x % no3 == 0:
            for a in range(1, int(no3)):
                if no3 % a == 0:
                    i = i + 1
            if i == 1:
                my_list.append(no3)
    print(max(my_list))

prime_factors(600851475143)

Он отлично работает для небольших чисел, но для большого числа, такого как этот «600851475143», код не дает вывода, он просто продолжает работать. Я хочу знать, в чем проблема с этим кодом и как я могу ее решить.


python primes prime-factoring
person Tejas Agarwal    schedule 24.06.2018    source источник
comment
Это число относительно велико, и ваш код должен перебирать множество чисел в первом цикле (подсказка: вам не нужно столько чисел) и множество чисел во втором цикле, поэтому для завершения может потребоваться довольно много времени. .   -  person ForceBru    schedule 25.06.2018
comment
Это может быть лучше на сайтах Code Golf или Software Engineering StackExchange.   -  person ryanwebjackson    schedule 25.06.2018
comment
Проводили ли какие-либо исследования? В одном только stackoverflow найдено более 300 обращений, просто выполнив поиск числа, которое вы пытаетесь учесть.   -  person Joseph Wood    schedule 25.06.2018

Ответы (1)


arrow_upward
1
arrow_downward

Каждый из ваших циклов от 2 до n, поэтому с 2 циклами ваш цикл должен выполняться квадрат (n) раз, прежде чем дать вам ответ

Если вы немного измените свой цикл, вы можете сделать это намного быстрее. Чтобы найти делители числа n, вам не нужно проверять все числа меньше n. Достаточно, если вы проверите до int(sqrt(n)). Для каждого фактора x между 2 и int(sqrt(n)), n/x также будет фактором.

Таким образом, изменив цикл так, чтобы он выполнялся только до int(sqrt(n)), ваш код будет работать намного быстрее.

from math import sqrt 

def is_prime(n): 
    for a in range(2, int(sqrt(n))): 
        if n % a == 0: 
            return False 
    return True 

def prime_factors(x): 
    my_list = [] 
    for no3 in range(2, int(sqrt(x))): 
        if x % no3 == 0: 
            # no3 and x/no3 are factors of x 
            if is_prime(no3): 
                my_list.append(no3) 
            if is_prime(x/no3): 
                my_list.append(no3) 
    print(max(my_list))

Теперь, попробовав это, мы получим

>>> prime_factors(600851475143)
6857
>>>
person Sunitha    schedule 25.06.2018
comment
Целевое число нечетное, поэтому у него нет четных множителей. При проверке возможных факторов начните с 3 и шага 2, чтобы проверялись только нечетные возможные факторы. Это должно вдвое сократить время поиска. - person rossum; 25.06.2018
comment
Да... Для этого можно сделать гораздо больше оптимизаций; но хотел максимально сохранить код в коде OP. Я надеюсь, что OP опробует ваше предложение и поэкспериментирует еще с несколькими - person Sunitha; 25.06.2018
comment
Спасибо @Sunitha ma'am за помощь, но проверка до квадратного корня из целевого числа не будет работать в случаях, когда квадратный корень меньше наибольшего множителя. Например, в случае числа 10 наибольший коэффициент равен 5, но квадратный корень равен 3,16, поэтому этот код вернет 2 в качестве вывода, хотя он должен был дать 5. - person Tejas Agarwal; 26.06.2018