Python判断数字是否是超级素数幂

温以宁

发布时间：2026-10-13| 6人浏览过

原创

本文介绍如何使用Python判断一个数字是否为超级素数幂，即该数字可表示为素数p的q次方（q>1）。通过先筛选小于根号n的素数，再逐一验证幂次关系，实现高效判断。文章包含完整代码示例及时间复杂度分析，帮助开发者理解算法逻辑与优化思路。

若某数字可表示为 p^q 的形式，其中 p 为素数，q 为大于 1 的正整数，则该数字称为超级素数幂。函数接收待测数字作为参数，若该数字不是超级素数幂，则返回 False；若是，则返回对应的 p 和 q 值。例如，输入 125，函数将返回 (5, 3)。

具体实现代码如下：

import math


def 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 prime

def 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 False

print super_prime_power(999)

算法逻辑分析如下：

该算法的总时间复杂度为 o(sqrt(n)log n)，加上寻找质数所花费的时间，总的时间复杂度为 o(n^2 sqrt(n)log n)。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。