Python Practice Example 14
Python 100 ExamplesProblem:Factorize a positive integer into prime factors. For example: input 90, print out 90=2*3*3*5.
Program analysis:To factorize n into prime factors, first find a smallest prime number k, then follow the steps below:
(1) If this prime number exactly equals n, it means the prime factorization process has ended; just print it out.
(2) If n<>k, but n is divisible by k, then print the value of k, and use the quotient of n divided by k as the new positive integer n, repeat the first step.
(3) If n is not divisible by k, use k+1 as the value of k, and repeat the first step.
Program source code:
Example (Python 2.0+)
#!/usr/bin/python
# -*- coding: UTF-8 -*-
def reduceNum(n):
print '{} = '.format(n),
if not isinstance(n, int) or n <= 0 :
print 'Please enter a correct number!'
exit(0)
elif n in [1] :
print '{}'.format(n)
while n not in [1] : # Loop ensures recursion
for index in xrange(2, n + 1) :
if n % index == 0:
n /= index # n equals n/index
if n == 1:
print index
else : # index must be a prime number
print '{} *'.format(index),
break
reduceNum(90)
reduceNum(100)
Example (Python 3.0+)
#!/usr/bin/python3
def reduceNum(n):
print ('{} = '.format(n), end=" ")
if not isinstance(n, int) or n <= 0 :
print ('Please enter a correct number!')
exit(0)
elif n in [1] :
print ('{}'.format(n))
while n not in [1] : # Loop ensures recursion
for index in range(2, n + 1) :
if n % index == 0:
n //= index # n equals n//index
if n == 1:
print (index )
else : # index must be a prime number
print ('{} *'.format(index), end=" ")
break
reduceNum(90)
reduceNum(100)
The output result of the above example is:
90 = 2 * 3 * 3 * 5 100 = 2 * 2 * 5 * 5Other extensions