Project Euler #3, infinite loop on factorization

Question

So I'm doing Project Euler because dear gods do I need to practice writing code, and also my math skills are rusty as something very rusty. Thusly; Project Euler. I'm sure most here have already seen or heard of the problem, but I'll put it here just for completeness:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

For this, I've written two functions:

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

This just checks any fed number for primality. It's working as intended (as far as I know), but now that I've said that I grow unsure. Anyway, it checks for special cases first: 1 (never prime), 2 (prime) or if it's divisible by 2 (not prime). If none of the special cases happen, it runs a general primality test.

This is my factorization code:

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

And this is definitely not working as intended. It is, sadly, working for the particular value of the Project Euler problem, but it doesn't work for, say, 100. I'm unsure what I need to do to fix this: what happens is that if it's a number like 100, it will correctly find the first 5 (2*2*5), but after that will loop around and set x = 7, which will make the entire thing loop infinitely because the answer is 2*2*5*5. Would recursion help here? I tried it, but it didn't get any prettier (it would still go into an endless loop for some numbers). I'm unsure how to solve this now.

I'm confused, what is `n = n` supposed to do? You're also not ever assigning anything to `n`. — slugonamission, Dec 02 '11 at 01:31
@slugonamission // is not a comment in python, it's int division. n = n / x would result in a float, // results in an int — Cassandra S., Dec 02 '11 at 01:34
How are you using the factorization() function? What is it supposed to return? The one I wrote for Euler-3 is recursive and returns a list of prime factors. — Russell Borogove, Dec 02 '11 at 01:46
To extra confusion with the SO syntax highlighter you could use `n//=x` — John La Rooy, Dec 02 '11 at 01:52

score 2 · Accepted Answer · answered Dec 02 '11 at 01:41

You're on a good track, but you need to take account of the possibility of repeating factors. You can do that with something like this:

factors = []

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

The idea here being that you're going to continue adding 2's to the factor list until the number you're testing becomes odd. You can use similar logic for other factors as well to enhance your factorization method.

score 1 · Answer 2 · answered Dec 02 '11 at 01:59

I think you have made the problem more complicated than necessary

Here is some pseudo code that you should be able to turn into Python code

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

score 0 · Answer 3 · answered Jun 28 '15 at 10:57

Here is another optimized solution:

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

rewritten · Answer 4 · 2011-12-02T01:50:26.513

For the repeating (odd) factors, just increment x when a divisor has not been found:

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, it seems that you miss always the "2" factors. Stick them on top and then do the main loop

EDIT (after comment)

You can do a much simpler:

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

By the way, you don't need the `isprime()` test at all. If you check divisors from 2 up to what needed, you are guaranteed that whenever `n % x == 0` then x is prime. If it wasn't, n should have been divided by the factors of x much before! — rewritten, Dec 02 '11 at 01:46

Project Euler #3, infinite loop on factorization

4 Answers4

Linked