python判斷數(shù)字是否是超級素?cái)?shù)冪
更新時(shí)間：2018年09月27日 14:49:46 作者：冬日新雨
這篇文章主要為大家詳細(xì)介紹了python判斷數(shù)字是否是超級素?cái)?shù)冪，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
如果一個數(shù)字能表示成 p^q，且p是一個素?cái)?shù)，q為大于1的正整數(shù)，則此數(shù)字就是超級素?cái)?shù)冪。
param number: 測試該數(shù)字是否是超級素?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))) # 開根號除掉一部分不需要的數(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)
分析：
總的時(shí)間復(fù)雜度為o(sqrt(n)log n)，再加上尋找質(zhì)數(shù)花費(fèi)的時(shí)間，總的時(shí)間復(fù)雜度為o(n^2 sqrt(n)log n)
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了用C++封裝MySQL的API的教程,包括對語句拼裝器SQLJoin的介紹,需要的朋友可以參考下2015-05-05
python3使用requests模塊爬取頁面內(nèi)容的實(shí)戰(zhàn)演練
本篇文章主要介紹了python3使用requests模塊爬取頁面內(nèi)容的實(shí)戰(zhàn)演練，具有一定的參考價(jià)值，有興趣的可以了解一下2017-09-09
這篇文章主要為大家詳細(xì)介紹了wxPython實(shí)現(xiàn)窗口用圖片做背景，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-04-04
Python Opencv實(shí)戰(zhàn)之印章提取的實(shí)現(xiàn)
很多時(shí)候我們需要電子版的章，但有些同學(xué)并不會通過Photoshop摳圖獲取。因此本文將利用Python OpenCV來實(shí)現(xiàn)印章的提取，感興趣的可以了解一下2022-03-03
Django 實(shí)現(xiàn)圖片上傳和顯示過程詳解
這篇文章主要介紹了Django 實(shí)現(xiàn)圖片上傳和顯示過程詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-07-07
Python鍵值互換是一種對Python字典類型中鍵值對進(jìn)行反轉(zhuǎn)的技術(shù)，有時(shí)候，我們需要以值作為鍵，以鍵作為值來操作字典，這時(shí)候就需要用到鍵值互換的技術(shù)，本文主要介紹了Python鍵值互換的實(shí)現(xiàn)示例，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
這篇文章主要介紹了Python爬蟲入門教程02之筆趣閣小說爬取,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-01-01
本文給大家分享的是使用使用python實(shí)現(xiàn)省市三級菜單效果的代碼，非常的實(shí)用，有需要的小伙伴可以參考下。2016-01-01
python實(shí)現(xiàn)批量監(jiān)聽頁面并發(fā)送郵件
這篇文章主要為大家詳細(xì)介紹了python如何實(shí)現(xiàn)自動化批量監(jiān)聽頁面并發(fā)送郵件,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-11-11
Python實(shí)現(xiàn)基于SVM的分類器的方法
這篇文章主要介紹了Python實(shí)現(xiàn)基于SVM的分類器的方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07