python判斷數(shù)字是否是超級素數(shù)冪
更新時間：2018年09月27日 14:49:46 作者：冬日新雨
這篇文章主要為大家詳細(xì)介紹了python判斷數(shù)字是否是超級素數(shù)冪，具有一定的參考價值，感興趣的小伙伴們可以參考一下
如果一個數(shù)字能表示成 p^q，且p是一個素數(shù)，q為大于1的正整數(shù)，則此數(shù)字就是超級素數(shù)冪。
param number: 測試該數(shù)字是否是超級素數(shù)冪
return: 如果不是就返回 False，如果是就返回 p 和 q 值
例如，輸入125，返回（5，3）
代碼：
import math
def get_prime(number):
'''
尋找小于number的所有的質(zhì)數(shù)，時間復(fù)雜度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))) # 開根號除掉一部分不需要的數(shù)
prime_number = get_prime(scope)
be_tested = []
for i in prime_number: # 先將無法被整數(shù)的排除掉
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)
分析：
總的時間復(fù)雜度為o(sqrt(n)log n)，再加上尋找質(zhì)數(shù)花費的時間，總的時間復(fù)雜度為o(n^2 sqrt(n)log n)
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
flask?route對協(xié)議作用及設(shè)計思路
這篇文章主要為大家介紹了flask?route對協(xié)議作用及設(shè)計思路詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-07-07
python庫TextDistance量化文本之間的相似度算法探究
這篇文章主要為大家介紹了python庫TextDistance量化文本之間的相似度算法探究,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2024-01-01
pytorch中的scatter_add_函數(shù)的使用解讀
這篇文章主要介紹了pytorch中的scatter_add_函數(shù)的使用解讀，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-06-06
python獲取的html中都是\\u003e實現(xiàn)轉(zhuǎn)成正確字符
這篇文章主要介紹了python獲取的html中都是\\u003e實現(xiàn)轉(zhuǎn)成正確字符方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-07-07
Python中NameError: name ‘Image‘ is not&nb
本文主要介紹了Python中NameError: name ‘Image‘ is not defined的問題解決,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-06-06
下面小編就為大家?guī)硪黄仙Ｕ刾ython的私有公有屬性(必看篇)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-06-06
python scipy.spatial.distance 距離計算函數(shù) ?
本文主要介紹了python scipy.spatial.distance 距離計算函數(shù)，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
本文主要介紹了Python讀取中文路徑出現(xiàn)亂碼的問題解決,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-06-06
Python之tkinter列表框Listbox與滾動條Scrollbar解讀
這篇文章主要介紹了Python之tkinter列表框Listbox與滾動條Scrollbar解讀，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-05-05
今天小編就為大家分享一篇Python 獲取numpy.array索引值的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12