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

yipeiwu_com7年前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)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

python3实现带多张图片、附件的邮件发送

本文实例为大家分享了python3实现多张图片附件邮件发送的具体代码,供大家参考,具体内容如下 直接上代码,没有注释! from email.mime.text import MIM...

详解Python的Django框架中的模版相关知识

HTML被直接硬编码在 Python 代码之中。 def current_datetime(request): now = datetime.datetime.now() h...

python自动翻译实现方法

本文实例讲述了python自动翻译实现方法。分享给大家供大家参考,具体如下: 以前学过python的基础,一般也没用过。后来有一个参数表需要中英文。想了一下,还是用python做吧。调用...

Python 正则表达式(转义问题)

先说一个比较囧的事情:在写虾米音乐试听下载器的时候遇到一个问题,因为保存的文件都是用音乐的标题命名的,所以碰到一些诸如「対峙/out border」等含有非法字符(哼哼,说的就是你 →_...

python设计tcp数据包协议类的例子

python设计tcp数据包协议类的例子

一. 问题描述 在tcp编程中,最需要解决的就是粘包分包问题。所以,我们需要在每个数据包前面加上数据包的长度用以分割粘连的包。 二. 包结构的设计 包的组成:包长度+数据域 包长度:用4...