Проблема с кодом Python для поиска наибольшего простого множителя числа (проблема 3 проекта Эйлера)

В настоящее время я пытаюсь решить проблему 3 проекта Эйлера с помощью python, который пытается найти наибольшее простое число фактор числа. Метод, который я использую, по сути является грубым форсированием каждого целого числа, меньшего, чем рассматриваемое целое число, проверяя, является ли оно множителем указанного целого числа, а затем проверяя, является ли оно простым. Однако по какой-то причине мой код не работает.

Я попытался создать функцию, которая проходит через каждое целое число (i) меньше заданного целого числа (n), и если i делится на n, функция затем переходит к проверке, является ли i простым числом, проходя через каждое целое число, меньшее или равное i (x). если x является множителем i, то значение добавляется к целому числу с нулевым значением, определенному как (a). После этого, если в итоге a складывается до i + 1, то это означает, что множитель является простым, поскольку делимыми числами были только он сам и 1. Код выглядит следующим образом:

def primefactor(n):
    for i in range(1, n+1): #goes through each integer less than n
        if n % i == 0: #checks if integer is a factor
            for x in range(1, i+1):  #another loop to check if the factor is prime
                a = 0
                primenumbers = []
                if i % x == 0:
                    a += x
                if a == i + 1:
                    primenumbers.append(i)
    print(primenumbers)

primefactor(13195)

Я ожидал, что на выходе он напечатает список всех простых множителей числа, в данном случае [5, 7, 13, 29], но вместо этого все, что я получил, был пустым списком []


python prime-factoring
person Mohammad Al-Sharif    schedule 11.05.2019    source источник
comment
primenumbers = [] вы превращаете primenumbers в пустой список в каждом цикле ....   -  person Error - Syntactical Remorse    schedule 12.05.2019

Ответы (1)


arrow_upward
0
arrow_downward

Эта проблема с вашим кодом заключается в том, что вы назначаете primenumbers пустому списку на каждой итерации с primenumbers = [].

Кроме того, если вы не хотите использовать грубую силу, хороший способ найти такие решения - это ввести в Google такую ​​формулу, как Формула для простых чисел, и вы найдете:

По теореме Вильсона n+1 является простым тогда и только тогда, когда n! mod(n + 1) = n.

Итак, вы можете сделать что-то вроде этого:

# This is just used as caching to make it faster
# it is not needed.
from functools import lru_cache
from math import factorial

@lru_cache()
def isprime(x):
    n = x - 1
    if n == factorial(n) % (n + 1):
        return True
    else:
        return False

def primefactor(n):
    primenumbers = []
    for i in range(1, n + 1): #goes through each integer less than n
        if n % i == 0: #checks if integer is a factor
            isprime(i) and primenumbers.append(i)
    print(primenumbers)

primefactor(13195)

Вывод:

[1, 5, 7, 13, 29]

Существуют также значительно более быстрые решения, чем это, такие, которые проходят через все числа от 0 до n: Алгоритм поиска наибольшего простого множителя числа

person Error - Syntactical Remorse    schedule 11.05.2019