pythonは数字がスーパー素数のべき乗かどうかを判断します。
p^qとして表され、pが素数であり、qが1より大きい正の整数である場合、この数字はスーパー素数のべき乗である。
パラムnumber:この数字がスーパー素数のべき乗かどうかをテストします。
return:そうでなければFalseに戻り、pとqの値を返します。
例えば、入力125は、(5、3)を返します。
コード:
全体の時間の複雑さはo(sqrt(n)logn)で、素数を探す時間も含めて、全体の時間の複雑さはo(n^2 sqrt(n)logn)である。
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。
パラムnumber:この数字がスーパー素数のべき乗かどうかをテストします。
return:そうでなければFalseに戻り、pとqの値を返します。
例えば、入力125は、(5、3)を返します。
コード:
import math
def get_prime(number):
'''
number , o(n^2)
'''
if number <= 1:
print 'Wrong given number.'
return
prime = []
for i in xrange(2, number+1):
j = 2
while j < i:
if i % j == 0:
break
j += 1
if j == i:
prime.append(i)
return prime
def super_prime_power(number):
scope = int(math.ceil(math.sqrt(number))) #
prime_number = get_prime(scope)
be_tested = []
for i in prime_number: #
if number % i == 0:
be_tested.append(i)
for p in be_tested:
q = 2
while p ** q <= number:
if p ** q == number:
return (p, q)
q += 1
return False
print super_prime_power(999)
分析:全体の時間の複雑さはo(sqrt(n)logn)で、素数を探す時間も含めて、全体の時間の複雑さはo(n^2 sqrt(n)logn)である。
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。