Welcome, guest | Sign In | My Account | Store | Cart

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

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

Created by gian paolo ciceri on Thu, 21 Apr 2005 (PSF)
Python recipes (4591)
gian paolo ciceri's recipes (7)

Required Modules

  • (none specified)

Other Information and Tasks