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

相关文章

python 实现查询Neo4j多节点的多层关系

python 实现查询Neo4j多节点的多层关系

需求:查询出满足3人及3案有关系的集合 # -*- coding: utf-8 -*- from py2neo import Graph import psycopg2 # 二维数...

python通过paramiko复制远程文件及文件目录到本地

最近写运维自动化平台,需要用python写很多的小功能模块。 这里就分享一个用Python的paramiko来实现功能的一段代码: 复制远程服务器上的文件及文件夹到本地目录。 解释一下什...

Python中的Numpy矩阵操作

Numpy 通过观察Python的自有数据类型,我们可以发现Python原生并不提供多维数组的操作,那么为了处理矩阵,就需要使用第三方提供的相关的包。 NumPy 是一个非常优秀的提...

横向对比分析Python解析XML的四种方式

横向对比分析Python解析XML的四种方式

在最初学习PYTHON的时候,只知道有DOM和SAX两种解析方法,但是其效率都不够理想,由于需要处理的文件数量太大,这两种方式耗时太高无法接受。 在网络搜索后发现,目前应用比较广泛,且效...

Python实现控制台中的进度条功能代码

Python实现控制台中的进度条功能代码

进度条最主要的问题就是所有字符全部在同一行,而且可以修改。 然而当执行print语句的时候,python会在打印完这个语句的同时在结尾加上‘\n',也就是换行,这就导致在控制台下一旦被p...