如果一個數字能表示成 p^q，且p是一個素數，q為大于1的正整數，則此數字就是超級素數冪。
param number: 測試該數字是否是超級素數冪
return: 如果不是就返回 False，如果是就返回 p 和 q 值
例如，輸入125，返回（5，3）
代碼：
import mathdef 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 primedef 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 Falseprint super_prime_power(999)
分析：
總的時間復雜度為o(sqrt(n)log n)，再加上尋找質數花費的時間，總的時間復雜度為o(n^2 sqrt(n)log n)
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持VEVB武林網。
新聞熱點
疑難解答
