primepow(aNumber) finds the prime number P and power N of aNumber such that aNumber = P^N.
The implementation is heavily borrowed from Art Owen <a href="http://www.csit.fsu.edu/~burkardt/cpp_src/oa/oa.html">Orthogonal Arrays Library</a>. It requires the <a href="http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/410662">isprime()</a> function.
Python, 29 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | def primepow(aNumber):
'''finds the prime base P and power N such that aNumber = P^N.'''
firstfactor = 0
p = 0
n = 0
if aNumber <= 1:
return False
if isprime(aNumber):
p = aNumber
n = 1
return (p, n)
else:
for k in xrange(2, int(math.sqrt(aNumber+1))+1):
if ( ( aNumber % k ) == 0 ):
firstfactor = k
break
if ( False == isprime( firstfactor ) ):
return False
q = aNumber
while( True ):
if q == 1:
return (firstfactor, n)
if (q % firstfactor) == 0:
n = n + 1
q = q / firstfactor
else:
return False
|
Please see Art Owen Orthogonal Array Library for details and sample of utilization.
Tags: algorithms
