ActiveState Code

Recipe 410663: A function to check if a number is a power of a prime

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 
 1
 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

Discussion

Please see Art Owen Orthogonal Array Library for details and sample of utilization.

Sign in to comment