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

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

相关文章

Python通过select实现异步IO的方法

本文实例讲述了Python通过select实现异步IO的方法。分享给大家供大家参考。具体如下: 在Python中使用select与poll比起在C中使用简单得多。select函数的参数是...

Python3基础之基本数据类型概述

本文针对Python3中基本数据类型进行实例介绍,这些对于Python初学者而言是必须掌握的知识,具体内容如下: 首先,Python中的变量不需要声明。每个变量在使用前都必须赋值,变量赋...

python3.4.3下逐行读入txt文本并去重的方法

python3.4.3下逐行读入txt文本并去重的方法

读写文件时应注意的问题包括: 1.字符编码 2.操作完成即时关闭文件描述符 3.代码兼容性 几种方法: #!/bin/python3 original_list1=[" "] ori...

Python连接DB2数据库

Python连接DB2数据库

在工作中遇到了这样的情况,项目中需要连接IBM的关系型数据库(DB2),关于这方面的库比较稀少,其中 ibm_db 是比较好用的一个库,网上也有教程,但是好像不准确,也不太详细,错误百出...

Python中类的创建和实例化操作示例

本文实例讲述了Python中类的创建和实例化操作。分享给大家供大家参考,具体如下: python中同样使用关键字class创建一个类,类名称第一个字母大写,可以带括号也可以不带括号; p...