python判断数字是否是超级素数幂_Python

如果一个数字能表示成 p^q，且p是一个素数，q为大于1的正整数，则此数字就是超级素数幂。
param number: 测试该数字是否是超级素数幂
return: 如果不是就返回 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)

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

原文链接：https://blog.csdn.net/dongrixinyu/article/details/78737849

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

相关文章

热门资讯