Prime Factorization Algorithm

• if ''n'' is prime, this is the factorization, so stop here.


• if ''n'' is composite, divide ''n'' by the first prime ''p''₁. If it divides cleanly, recurse with the value ''n''/''p''₁. Add ''p''₁ to the list of factors obtained for ''n''/''p''₁ to get a factorization for n. If it does not divide cleanly, divide ''n'' by the next prime ''p''₂, and so on.

import sys

from math import sqrt

def factorize(n):

    def isPrime(n):

        return not  for x in xrange(2,int(sqrt(n))+1) if n%x == 0 

    primes =  {Link without Title} 

    candidates = xrange(2,n+1)

    candidate = 2

    while not primes and candidate in candidates:

        if n%candidate == 0 and isPrime(candidate):

            primes = primes +  {Link without Title}  + factorize(n/candidate)

        candidate += 1            

    return primes

print factorize(int(sys.argv {Link without Title} ))

python factorize.py 9438

 3, 11, 11, 13 

import sys



ListOfPrimes= {Link without Title} 

maxindex=len(ListOfPrimes)

maxprimeinlist=ListOfPrimes {Link without Title} 



# Put Primes in a dictionary

DictPrime={}

DictPrime.fromkeys(ListOfPrimes,True)



def intsqrt(n):

  """ Return the integer square root of a long number """

  def intsqrt_core(digitpair,remainder,results):

    # function intsqrt_core returns (results,remainder)

    if digitpair<100:


100 + digitpair


      for d in range(9,-1,-1):




10---results + d)---d


        if x <= currvalue:



          remainder= currvalue - x


10 + d


          return(results,remainder)



    else:

      (results,remainder)=intsqrt_core(digitpair//100,remainder,results)

      (results,remainder)=intsqrt_core(digitpair%100,remainder,results)

      return(results,remainder)

  (results,remainder)=intsqrt_core(n,0,0)

  return results



def isPrime(n):

  """ Return True if n is a prime """

  if DictPrime.has_key(n):

    return True

  high=intsqrt(n)

  for x in ListOfPrimes:

    if x <= high and n%x == 0:

      return False

    if x >= high:

      return True

  x=maxprimeinlist + 2

  while x<=high:

    if n%x == 0:

      return False

    x += 2

  return True



def factorize(n):

  """ Factorize an integer number """

  primes =  {Link without Title} 

  index=0

  candidate = ListOfPrimes {Link without Title} 

  while not primes and candidate <= n:

    if n%candidate == 0 and (index < maxindex or isPrime(candidate)):

      primes = primes +  {Link without Title}  + factorize(n//candidate)

    index += 1            

    if index < maxindex:

      candidate = ListOfPrimes {Link without Title} 

    else:

      candidate += 2

  return primes



def condense(L):

  """ Condense result in list to prime^nth_power format """

  prime,count,list=0,0, {Link without Title} 

  for x in L:

    if x == prime:

      count += 1

    else:

      if prime != 0:

        list = list +  + '^' + str(count) 

      prime,count=x,1

  list = list +  + '^' + str(count) 

  return list



if __name__ == '__main__':

  print condense(factorize(long(sys.argv {Link without Title} )))



# Sample output

#

# python factorize.py 173248246132375748867198458668657948626531982421875

#  '5^14', '7^33', '13^1' 

• Euler's Theorem


• Integer Factorization


• Trial Division

• Prime factorization at Mathworld


• Factorization solver implementing the algorithm described here, work shown


• Factorizer Windows software to decompose numbers up to 2,147,483,646 into their prime constituents


• Factoris , online prime factorizer