Prime factorization - list

Question

I am trying to implement a function primeFac() that takes as input a positive integer n and returns a list containing all the numbers in the prime factorization of n.

I have gotten this far but I think it would be better to use recursion here, not sure how to create a recursive code here, what would be the base case? to start with.

My code:

def primes(n):
    primfac = []
    d = 2
    while (n > 1):
         if n%d==0:
             primfac.append(d)
    # how do I continue from here... ?

Entozoic

If you're just looking for prime factorization in python (no recursion needed): https://mcmap.net/q/126945/-algorithm-to-find-largest-prime-factor-of-a-number – Osgood

Unbounded recursion generally isn't a good idea in Python. By default, you're limited to 1000 stack frames. – Panegyric

Try a list comprehension – Knotts

im sorry im very new to Python... im just having problem with covering all possible primefactors..how do i finish my code – Entozoic

Does this answer your question? Fast prime factorization module – Beisel

Answer 1

A simple trial division:

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

with O(sqrt(n)) complexity (worst case). You can easily improve it by special-casing 2 and looping only over odd d (or special-casing more small primes and looping over fewer possible divisors).

Postoperative

daniel, what does this mean exactly ( n /= d )... sorry – Entozoic

It means "divide n by d and let n refer to the quotient henceforth". Just like +=, only with division instead of addition. – Postoperative

i like your answer, and im trying to decipher it. So why do you write d*d ? what is the point with doubling d? – Entozoic

and why do I need two while loops? – Entozoic

@Entozoic the inner loop counts each factor up to its multiplicity - eg, it causes primes(12) to give [2, 2, 3] instead of [2, 3], and primes(27) to give [3, 3, 3] instead of [3]. – Adscription

@Entozoic for the d*d, notice that this doesn't double d, it squares it. The condition is equivalent to d <= sqrt(n). It is provable that any n has at most one prime factor that doesn't meet this. The nested loops divide out each prime factor as it is found, leaving the quotient in n. That means at the point where the loop exits, if there is a factor left (and the only options are one or none), it will be n. OTOH, if all of the factors have been found, they will all have been divided out, and n must be 1. – Adscription

if(x): while(x): is redundant, though I don't understand why that suggestion was rejected – Childers

This can be sped up to run in about half the time just by factoring out 2 at the beginning, starting f at 3, and then incrementing it by 2 instead of 1 every time. – Dimitri

prime(18) returns [2, 3, 3] as opposed to [2, 3, 5, 7, 11, 13, 17] – Experimentation

@StanBashtavenko The name of the function (which comes from the OP) may be misleading, but its purpose is to give the prime factorisation of the argument, not the list of primes up to the argument. – Postoperative

May I ask what's the reason for using d * d <= n instead of d <= n here? The power of a prime factor p may be just 1 and d * d <= n will let go of p. I saw you have an additional catcher if n > 1: ... at the end, but in my opinion the most natural way should be setting d <= n instead as the loop condition from the outset. – Spadework

Answer 2

The primefac module does factorizations with all the fancy techniques mathematicians have developed over the centuries:

#!python

import primefac
import sys

n = int( sys.argv[1] )
factors = list( primefac.primefac(n) )
print '\n'.join(map(str, factors))

Bothwell

Here's another example: [factor for factor in primefac.primefac(2016)] returns a list of factors: [2, 2, 2, 2, 2, 3, 3, 7] – Quamash

If you want to turn a generator into a list, you can use list(primefac.primefac(2016)) – Antigua

The version on PyPi does not appear to be compatable with Python 3. There is a fork on github that is (here), which can be installed with pip3 install git+git://github.com/elliptic-shiho/primefac-fork@master – Davedaveda

If you want PyPI and no problems with Python3: testpypi.python.org/pypi/pyprimesieve/0.1.6c0 - pyprimesieve also looks promising. – Gymkhana

@Davedaveda Meanwhile, primefac is Python3 compatible. – Varden

Answer 3

This is a comprehension based solution, it might be the closest you can get to a recursive solution in Python while being possible to use for large numbers.

You can get proper divisors with one line:

divisors = [ d for d in xrange(2,int(math.sqrt(n))) if n % d == 0 ]

then we can test for a number in divisors to be prime:

def isprime(d): return all( d % od != 0 for od in divisors if od != d )

which tests that no other divisors divides d.

Then we can filter prime divisors:

prime_divisors = [ d for d in divisors if isprime(d) ]

Of course, it can be combined in a single function:

def primes(n):
    divisors = [ d for d in range(2,n//2+1) if n % d == 0 ]
    return [ d for d in divisors if \
             all( d % od != 0 for od in divisors if od != d ) ]

Here, the \ is there to break the line without messing with Python indentation.

Creaturely

ok, so why ( d for d ) i dont understand what this does? like i said earlier, i am very new to python.... i really appriciate your help – Entozoic

[ d for d in l if P(d) ] constructs the list of elements in d such that P(d) holds. For example, [ n for n in range(20) where n % 2 == 0 ] constructs the list of even numbers < 20. – Creaturely

but this algorithm won't repeat primes. for the input of 4, it returns [2]. – Laryngotomy

Missing closing parentheses on the first one liner – Reside

Nice one. Can you please break down this line all( d % od != 0 for od in divisors if od != d ) step by step explaining what it does. It is really complex for someone new to python like me. – Lavaliere

Answer 4

I've tweaked @user448810's answer to use iterators from itertools (and python3.4, but it should be back-portable). The solution is about 15% faster.

import itertools

def factors(n):
    f = 2
    increments = itertools.chain([1,2,2], itertools.cycle([4,2,4,2,4,6,2,6]))
    for incr in increments:
        if f*f > n:
            break
        while n % f == 0:
            yield f
            n //= f
        f += incr
    if n > 1:
        yield n

Note that this returns an iterable, not a list. Wrap it in list() if that's what you want.

Photic

Answer 5

Here is my version of factorization by trial division, which incorporates the optimization of dividing only by two and the odd integers proposed by Daniel Fischer:

def factors(n):
    f, fs = 3, []
    while n % 2 == 0:
        fs.append(2)
        n /= 2
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += 2
    if n > 1: fs.append(n)
    return fs

An improvement on trial division by two and the odd numbers is wheel factorization, which uses a cyclic set of gaps between potential primes to greatly reduce the number of trial divisions. Here we use a 2,3,5-wheel:

def factors(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs

Thus, print factors(13290059) will output [3119, 4261]. Factoring wheels have the same O(sqrt(n)) time complexity as normal trial division, but will be two or three times faster in practice.

I've done a lot of work with prime numbers at my blog. Please feel free to visit and study.

Mai

Thanks for the great solution there. I hope you don't mind that I tweaked it a bit to use itertools (and python3.4). Can't paste code here, so I"ll add it a little later in response. – Photic

Nice one. If possible can you please break down the second function step by step? It's really hard to understand for someone new to python. Please. – Lavaliere

It's a simple implementation of a prime wheel, with the wheel stored in gaps. The while loops implements trial division, but the next trial divisor f is incremented according to the wheel. The current position on the wheel is nxt, which is incremented each time but then cycles back at the end of the wheel. – Mai

Answer 6

Most of the above solutions appear somewhat incomplete. A prime factorization would repeat each prime factor of the number (e.g. 9 = [3 3]).

Also, the above solutions could be written as lazy functions for implementation convenience.

The use sieve Of Eratosthenes to find primes to test is optimal, but; the above implementation used more memory than necessary.

I'm not certain if/how "wheel factorization" would be superior to applying only prime factors, for division tests of n.

While these solution are indeed helpful, I'd suggest the following two functions -

Function-1 :

def primes(n):
    if n < 2: return
    yield 2
    plist = [2]
    for i in range(3,n):
        test = True
        for j in plist:
            if j>n**0.5:
                break
            if i%j==0:
                test = False
                break
        if test:
            plist.append(i)
            yield i

Function-2 :

def pfactors(n):
    for p in primes(n):
        while n%p==0:
            yield p
            n=n//p
            if n==1: return

list(pfactors(99999))
[3, 3, 41, 271]

3*3*41*271
99999

list(pfactors(13290059))
[3119, 4261]

3119*4261
13290059

Uxorial

Answer 7

def get_prime_factors(number):
    """
    Return prime factor list for a given number
        number - an integer number
        Example: get_prime_factors(8) --> [2, 2, 2].
    """
    if number == 1:
        return []

    # We have to begin with 2 instead of 1 or 0
    # to avoid the calls infinite or the division by 0
    for i in xrange(2, number):
        # Get remainder and quotient
        rd, qt = divmod(number, i)
        if not qt: # if equal to zero
            return [i] + get_prime_factors(rd)

    return [number]

Berkeleian

If rd stands for remainder and qt stand for quotient, you've mixed up both variables. Divmod gives the quotient first and the remainder second. You also have to check if the remainder is equal to zero (it is fully dividable by the current range value), not the quotient. Your solution works as expected, but the variable names are switched. – Malachite

Answer 8

Most of the answer are making things too complex. We can do this

def prime_factors(n):
    num = []

    #add 2 to list or prime factors and remove all even numbers(like sieve of ertosthenes)
    while(n%2 == 0):
        num.append(2)
        n /= 2

    #divide by odd numbers and remove all of their multiples increment by 2 if no perfectlly devides add it
    for i in xrange(3, int(sqrt(n))+1, 2):
        while (n%i == 0):
            num.append(i)
            n /= i

    #if no is > 2 i.e no is a prime number that is only divisible by itself add it
    if n>2:
        num.append(n)

    print (num)

Algorithm from GeeksforGeeks

Romilda

Answer 9

prime factors of a number:

def primefactors(x):
    factorlist=[]
    loop=2
    while loop<=x:
        if x%loop==0:
            x//=loop
            factorlist.append(loop)
        else:
            loop+=1
    return factorlist

x = int(input())
alist=primefactors(x)
print(alist)

You'll get the list. If you want to get the pairs of prime factors of a number try this: http://pythonplanet.blogspot.in/2015/09/list-of-all-unique-pairs-of-prime.html

Transudation

Answer 10

def factorize(n):
  for f in range(2,n//2+1):
    while n%f == 0:
      n //= f
      yield f

It's slow but dead simple. If you want to create a command-line utility, you could do:

import sys
[print(i) for i in factorize(int(sys.argv[1]))]

Farouche

why is two // in for loop "n//2"? – Solitary

try it with 600851475143, Project euler 3rd problem.. range will bust – Solitary

@DevC: The // is a python 3 construct, where range is the same as xrange in py2. Would have been self-evident if you had looked at the second chunk of code, as print in list comprehension doesn't work in py2. – Boffa

Answer 11

Here is an efficient way to accomplish what you need:

def prime_factors(n): 
  l = []
  if n < 2: return l
  if n&1==0:
    l.append(2)
    while n&1==0: n>>=1
  i = 3
  m = int(math.sqrt(n))+1
  while i < m:
    if n%i==0:
      l.append(i)
      while n%i==0: n//=i
    i+= 2
    m = int(math.sqrt(n))+1
  if n>2: l.append(n)
  return l

prime_factors(198765430488765430290) = [2, 3, 5, 7, 11, 13, 19, 23, 3607, 3803, 52579]

Bathilda

Answer 12

    from sets import Set
    # this function generates all the possible factors of a required number x
    def factors_mult(X):
        L = []
        [L.append(i) for i in range(2,X) if X % i == 0]
        return L

    # this function generates list containing prime numbers upto the required number x 
    def prime_range(X):
        l = [2]
        for i in range(3,X+1):
            for j in range(2,i):
               if i % j == 0:
               break
            else:    
               l.append(i)
        return l

    # This function computes the intersection of the two lists by invoking Set from the sets module
    def prime_factors(X):
        y = Set(prime_range(X))
        z = Set(factors_mult(X))
        k = list(y & z)
        k = sorted(k)

        print "The prime factors of " + str(X) + " is ", k

    # for eg
    prime_factors(356)

Fillip

I would recommend you to add an explanation on how this piece of code helps. – Duma

definitely I'll add some comments in the code section – Fillip

Answer 13

Simple way to get the desired solution

def Factor(n):
    d = 2
    factors = []
    while n >= d*d:
        if n % d == 0:
            n//=d
            # print(d,end = " ")
            factors.append(d)
        else:
            d = d+1
    if n>1:
        # print(int(n))
        factors.append(n)
    return factors

Mcdonald

Answer 14

This is the code I made. It works fine for numbers with small primes, but it takes a while for numbers with primes in the millions.

def pfactor(num):
div = 2
pflist = []
while div <= num:
    if num % div == 0:
        pflist.append(div)
        num /= div
    else:
        div += 1
# The stuff afterwards is just to convert the list of primes into an expression
pfex = ''
for item in list(set(pflist)):
    pfex += str(item) + '^' + str(pflist.count(item)) + ' * '
pfex = pfex[0:-3]
return pfex

Doradorado

Please indent your code properly. Also in Python 3.x num /= div produces a float, not an integer. And testing all divisors instead of 2 and odd numbers is not the most efficient strategy. – Kippar

Answer 15

I would like to share my code for finding the prime factors of number given input by the user:

a = int(input("Enter a number: "))

def prime(a):
    b = list()
    i = 1
    while i<=a:
        if a%i ==0 and i!=1 and i!=a:
            b.append(i)
        i+=1
    return b

c = list()
for x in prime(a):
    if len(prime(x)) == 0:
        c.append(x)

print(c)

Mobile

Answer 16

def prime_factors(num, dd=2):
    while dd <= num and num>1:
        if num % dd == 0:
            num //= dd
            yield dd
        dd +=1

Lot of answers above fail on small primes, e.g. 3, 5 and 7. The above is succinct and fast enough for ordinary use.

print list(prime_factors(3))

[3]

Acupuncture

Answer 17

You can use sieve Of Eratosthenes to generate all the primes up to (n/2) + 1 and then use a list comprehension to get all the prime factors:

def rwh_primes2(n):
    # https://mcmap.net/q/86560/-fastest-way-to-list-all-primes-below-n/3035188#3035188
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    correction = (n%6>1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n/3)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      ((k*k)/3)      ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
        sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
    return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]

def primeFacs(n):
    primes = rwh_primes2((n/2)+1)
    return [x for x in primes if n%x == 0]

print primeFacs(99999)
#[3, 41, 271]

Maxson

Seriously? Sieve to n/2 to find the prime factors? – Postoperative

Is a cool solution... I would prefer a generator though for the sieve instead of returning a list. – Cheeseburger