溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
如果一個數字能表示成 p^q，且p是一個素數，q為大于1的正整數，則此數字就是超級素數冪。
param 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)log n)，再加上尋找質數花費的時間，總的時間復雜度為o(n^2 sqrt(n)log n)
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
