_10_factorize Namespace Reference

A simple factorization algorithm. More...

Functions
def	factorize_rec (n)
	Factorizes an integer or long number. More...
def	factorize (n)
	Factorizes an integer or long number. More...
def	condense (L)
	Condenses the list of prime factors of a number, so that each factor appears just once, in the format \(prime^{nth_{power}}\). More...
def	main (argv=None)
	main function for testing. More...

Variables
	input = raw_input

Detailed Description

A simple factorization algorithm.

1. If n is prime, this is the factorization, so stop here.
   
2. If n is composite, divide n by the first prime p1.
   
3. If it divides cleanly, recurse with the value n/p1.
   
4. Add p1 to the list of factors obtained for n/p1 to get a factorization for n.
   
5. If it does not divide cleanly, divide n by the next prime p2, and so on.

Note that we need to test only primes \(\pi\) such that \(\pi \le \sqrt(n)\).

Author

Paulo Roma

Since

27/12/2008

See also

https://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html

https://academickids.com/encyclopedia/index.php/Prime_factorization_algorithm

Function Documentation

condense()

def _10_factorize.condense

(

L

)

Condenses the list of prime factors of a number, so that each factor appears just once, in the format \(prime^{nth_{power}}\).

e.g., python factorize2.py 173248246132375748867198458668657948626531982421875
['3^24', '5^14', '7^33', '13']

Parameters

L	a list with the prime factors of a number.

Returns

a condensed list.

Referenced by main().

factorize()

def _10_factorize.factorize

(

n

)

Factorizes an integer or long number.

Non recursive version.

Parameters

n	given integer.

Returns

a list with the prime factors of n.

Referenced by main().

factorize_rec()

def _10_factorize.factorize_rec

(

n

)

Factorizes an integer or long number.

Recursive version.

Parameters

n	given integer.

Returns

a list with the prime factors of n.

main()

def _10_factorize.main

(

argv = None

)

main function for testing.

Parameters

argv

sys.argv

References condense(), factorize(), and input.

Variable Documentation

input

_10_factorize.input = raw_input

Referenced by main().