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设计】。

相关文章

windows下ipython的安装与使用详解

windows下ipython的安装与使用详解

ipython的安装 ipython可以直接使用pip install ipython安装 ,如果安装失败按如下步骤手动进行安装 所需文件下载:    ...

Python编程生成随机用户名及密码的方法示例

本文实例讲述了Python编程生成随机用户名及密码的方法。分享给大家供大家参考,具体如下: 方案一: import random global userName,userPasswo...

使用Fabric自动化部署Django项目的实现

文中涉及的示例代码,已同步更新到HelloGitHub-Team 仓库 在上一篇教程中,我们通过手工方式将代码部署到了服务器。整个过程涉及到十几条命令,输了 N 个字符。一旦我们本地的代...

Python函数中定义参数的四种方式

Python中函数参数的定义主要有四种方式: 1. F(arg1,arg2,…) 这是最常见的定义方式,一个函数可以定义任意个参数,每个参数间用逗号分割,用这种方式定义的函数在调用的的时...

python制作mysql数据迁移脚本

用python写了个数据迁移脚本,主要是利用从库将大的静态表导出表空间,载导入到目标实例中。 #!/usr/bin/env python3 #-*- coding:utf8 -*-...