Project Euler Problem 3

"The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?"

Let's start off by googling how to calculate prime factors in a good way. Maybe I need to start calculating prime numbers? Checking every number between 0 and 600851475143 to see if it's a prime number was a bad idea.

After some coding I've successfully produced the same result as in the example.

primeList = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79]
okPrimes = []
number = 13195
for x in range(1,len(primeList)):
    if number%primeList[x]==0:
        okPrimes.append(primeList[x])
        print("ok prime: ", primeList[x])

print("Number of ok primes: ", len(okPrimes))

which makes following output:

ok prime:  5
ok prime:  7
ok prime:  13
ok prime:  29
Number of ok primes:  4

I've hard coded the prime numbers into the list primeList. After consulting with an online prime factor calculator, I've found that the prime number that I'm looking for is way bigger than what I've hard coded. Now the question is if I should calculate my own prime numbers or if I should hard code them into the list.

Now that I'm checking remainder of 600851475143%x (for-loop), I'm getting really many ok prime numbers, and also on fewer lines of code!

okPrimes = []
number = 600851475143
for x in range(1,600851475143):
    if number%x==0:
        okPrimes.append(x)
        print("ok prime: ", x)

print("Number of ok primes: ", len(okPrimes))

Output:

ok prime:  1
ok prime:  71
ok prime:  839
ok prime:  1471
ok prime:  6857
ok prime:  59569
ok prime:  104441
ok prime:  486847
ok prime:  1234169
ok prime:  5753023
ok prime:  10086647
.... I stop it manually

Now I need to make it stop automatically when it have reached enough factors to multiply to 60085147514 (which are the five first in the above output). To do this in a nice way I want to check the product of all the okPrimes and check the remainder of 600851475143%(the product). Stack overflow suggests that I add the library functools and operator by adding "import functools" and  "import operator" in the beginning of my code to get access to the feature.

Success was reached with following code:

import functools
import operator

okPrimes = []
product = 1number = 600851475143largestFactor = 0
for x in range(1,600851475143):
    if number%x==0:
        okPrimes.append(x)
        product = functools.reduce(operator.mul, okPrimes)
    if product==number:
        break
for x in range(0,len(okPrimes)):
    if okPrimes[x]>largestFactor:
        largestFactor=okPrimes[x]

print(largestFactor)

with 20 lines. I could've skipped the last 6 lines and added a print on each okPrime instead, but this solution has a nicer output.

/Ludvig