溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

python判斷數(shù)字是否是超級素數(shù)冪

發(fā)布時間：2020-08-28 14:09:27 來源：腳本之家 閱讀：191 作者：冬日新雨 欄目：開發(fā)技術(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í)有所幫助，也希望大家多多支持億速云。

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手