Problem with python code for finding largest prime factor of a number (Project Euler problem 3)

Question

I'm currently trying to solve Project Euler problem 3 using python, which is trying to find the largest prime factor of a number. The method I'm using is essentially brute forcing my way through each integer less than the integer in question, checking if it's a factor of said integer, and then checking if it is prime. However, for some reason, my code doesn't seem to be working.

I've tried to use create a function which goes through each integer (i) less than a given integer (n), and if i is divisible by n, the function then proceeds to check if i is a prime number by going through every integer less or equal to i (x). if x is a factor of i, then the value is added to a zero-integer defined as (a). After that, if a ends up adding to equal i + 1, then that means the factor is prime, since the only numbers divisible were itself and 1. The code is as below:

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)

What i expected the output to be was for it to print a list of all of the prime factors of the number, in this case, [5, 7, 13, 29], but instead, all I got was an empty list, []

`primenumbers = []` you turn `primenumbers` into an empty list on every loop.... — Error - Syntactical Remorse, May 11 '19 at 23:32

Error - Syntactical Remorse · Answer 1 · 2019-05-11T23:59:39.760

This issue with your code is you assign primenumbers to an empty list each iteration with primenumbers = [].

Also if you don't want to brute force it, a good method to solve solutions like this is to google a formula such as Formula for primes and you will find:

By Wilson's theorem, n+1 is prime if and only if n! mod(n + 1) = n.

So you can do something like this:

# 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)

Output:

[1, 5, 7, 13, 29]

There are also significantly faster solutions then this such that does go through all numbers 0 to n: Algorithm to find Largest prime factor of a number

Problem with python code for finding largest prime factor of a number (Project Euler problem 3)

1 Answers1