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