Largest Prime Factor Python

Question

I'm trying to find the largest prime factor of a given number (600851475143) using Python. I've made the following code, but the problem is, it takes forever, probably because it's iterating through lists millions of times. How to optimize this process?

def factors(n):
    list = []
    i = 1
    while i < n:
        if n % i == 0:
            list.append(i)
        i += 1
    return list

def prime(n):
    list = factors(n)
    primelist = []
    for item in list[1:]:
        if item % 2 != 0 and item % 3 != 0 and item % 4 != 0 and item  \
        % 5 != 0 and item % 6 != 0 and item % 7 != 0 and item % 8 != 0 \
        and item % 9 != 0:
            primelist.append(item)
    return primelist

def greatestprime(n):
    list = prime(n)
    list[0] = lnum
    i = 1
    while i < len(list):
        if list[i] > lnum:
            lnum = list[i]
    return lnum

#print(greatestprime(600851475143))

Answer 1

If you are only factorizing a single number n, then the naive approach of testing every number from 2 to sqrt(n) (square root of n) should give result quickly for numbers up to 10¹⁴. You are writing more code than necessary.

Slightly better approaches would be:

• Test 2, then test every odd number
• Test 2, 3, 5, then test all integers of the form 6k + 1 and 6k + 5 where k >= 1
• The 2 approaches above are wheel factorization with n = 2 and n = 2*3 = 6 respectively. You can raise it up to to n = 2*3*5*7 = 210 (higher would not bring much efficiency).

Slightly better approach would be to generate primes via Eratosthenes sieve and test (no redundant test). There are even better approaches such as Pollard's rho factorization, but both methods are overkill unless you are working with more numbers.

Answer 2

Finding the largest prime factor of a number really isn't as difficult as people make it out to be.

from itertools import takewhile
from math import floor, sqrt

def _prime_numbers_helper():
    yield 2
    yield 3
    i = 1
    while True:
        yield 6 * i - 1
        yield 6 * i + 1
        i += 1

def prime_numbers(ceiling=None):
    if ceiling is None:
        yield from _prime_numbers_helper()
    else:
        yield from takewhile(lambda number: number <= ceiling, _prime_numbers_helper())

def largest_prime_factor(number):
    if number % int(number) != 0:
        raise ValueError('The number must be an integer.')
    if number in (0, 1):
        raise ValueError('There is no largest prime factor of {}.'.format(number))

    while True:
        for i in prime_numbers(floor(sqrt(abs(number)))):
            if number % i == 0:
                number //= i
                break
        else:
            return number

The else statement only executes when the for statement executes to completion (i.e. when the number cannot be factored any further).

The for statement should be using a true prime number generator instead, but I'm too lazy to write an efficient implementation of it.

Note that this assumes that you are using Python 3.3 or later.

Out of curiosity is this for Project Euler Problem 3?

Answer 3

It is easy to find the factors of n by trial division, as long as n isn't too large; the :: operator inserts f at the front of the fs linked list:

function factors(n)
    f, fs := 2, []
    while f * f <= n
        while n % f == 0
            n := n / f
            fs := f :: fs
        f := f + 1
    if n <> 1
        n :: fs
    return reverse(fs)

If you're interested in programming with prime numbers, or if you're looking for a library to help with the Project Euler problems that involve prime numbers, I modestly recommend this essay at my blog, which includes, among other things, a translation of the above pseudocode to Python:

def td_factors(n, limit=1000000):
    if type(n) != int and type(n) != long:
        raise TypeError('must be integer')
    fs = []
    while n % 2 == 0:
        fs += [2]
        n /= 2
    if n == 1:
        return fs
    f = 3
    while f * f <= n:
        if limit < f:
            raise OverflowError('limit exceeded')
        if n % f == 0:
            fs += [f]
            n /= f
        else:
            f += 2
    return fs + [n]

Answer 4

Here are 2 possibilities. One from this blog:

def gpf(n):
    """
    Find the greatest prime factor of n
    """
    if n < 2:
        raise ValueError('{} does not have a prime factorization'.format(n))
    divisor = 2
    while n > 1:
        if not n % divisor:
            n /= divisor
            divisor -= 1
        divisor += 1
    return divisor

your example:

In [15]: gpf(600851475143)
Out[15]: 6857

In [16]: timeit gpf(600851475143)
1000 loops, best of 3: 1.55 ms per loop

or using SymPy library:

from sympy import factorint
def gpf(n):
    return max(factorint(n).keys())

(note that this has defined behavior for n < 2)

Answer 5

Try:

number = whatever your number is
divisor = 2

while divisor < number:
    if number % divisor == 0:
        number /= divisor
    else:
        divisor += 1

You're dividing out numbers until it's not possible anymore - which is what they teach you to do in grade school for this type of problem (although they'd never ask you to do this trick on a 12 digit number). When you get to a number that

Seems weird at first, but it works: each pass you'll be both decreasing the size of the number that you're looking at and dividing out lesser primes. If the number is divisible by 32, for instance, you'll just divide 2 out 6 times before proceeding, and in doing so you'll shrink the pool of numbers that could be factors of number. In the case where your number is already its own largest prime factor, you'll still have to iterate up to it in order to verify that. In the normal case (number is a product of its largest prime and some composite number) you'll divide out all of its lesser factors before you even check that the largest prime divides it.

Another useful heuristic is to find the square root of your number and only check numbers less than that: it's impossible n > sqrt(number) for n that are (integer) factors of number. I like the first method, however.

sike, didn't see someone already posted a really similar solution.

Answer 6

This is how I went about it:

def is_prime(m):
    """Checks if the argument is a prime number."""

    if m < 2: return False

    for i in xrange(2, m):
        if m % i == 0:
            return False

    return True

def get_largest_prime_factor(k):
    """Gets the largest prime factor for the argument."""

    prime_divide = (p for p in xrange(1, k))
    for d in prime_divide:

        if k % d == 0 and is_prime(k / d):
            return k / d

print get_largest_prime_factor(600851475143)

Answer 7

n=int(input(""))

prime_factors=[]
for i in range(2,int(n**0.5+1)):
  if n%i==0:
    for x in range(2,int(i**0.5+1)): 
      if i%x==0:
        break
    else:
      prime_factors.append(i)
      
print("prime factors are:",prime_factors)
print("largest prime factor is",prime_factors[-1])

input : 600851475143
output: prime factors are: [71, 839, 1471, 6857]
largest prime factor is 6857

Answer 8

Actual Final Program: Uses long division old way to find factors and stores only the largest/current factor until last one is found.

I know this is an old question, but wanted to share my way of approaching the problem.

def prime_factors_old_fashioned_factorization(number):
    y=1
    for x in range(2,number):
        if(number%x==0):
            print("number=",number,"\t and X=",x)
            while(number%x==0):
                print("number=",number)
                number=number/x
            print("new number=",number)
            y=x
            x=x+1
            if((number==1) or (number<x)):
                break;
    print("largest prime factor=",y)

Answer 9

# Largest prime factor of a number
def prime_fact(n):
    p=[]
    f=[]
    p.append(1)
    for d in range(2,n+1):
        if n%d==0:
            f.append(d)

    for v in f:
        if (v==1 or v==2):
            p.append(v)
        else:
            for i in range(2,v):
                if v%i ==0:
                    break

            else:
                p.append(v)
    print(f'Factors of the number are {f}')
    print(f'Primefactors are {p}')
    print(f'Largest prime factor is {p[-1]}')