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:print格式化输出到文件的实例

遇到一个写文件的小程序,需要把print输出改成输出到文件,遇到这个问题的思路是把需要的字符串拼接到一个字符串中,然后在写到文件中,这样做觉得很麻烦,想到之前的学的exec的使用,但是实...

跟老齐学Python之编写类之二方法

跟老齐学Python之编写类之二方法

数据流转过程 除了在类中可以写这种函数之外,在类中还可以写别的函数,延续上一讲的例子: 复制代码 代码如下: #!/usr/bin/env python #coding:utf-8 cl...

python开发准备工作之配置虚拟环境(非常重要)

python开发准备工作之配置虚拟环境(非常重要)

之前作为菜鸟的我,从来不知道创建虚拟环境来开发python,都是使用全局的来开发项目,这样最后的结果是,所有的包全部安装在全局,也不能有好的在切换py2中切换,现在讲解在widow下使用...

python编程-将Python程序转化为可执行程序[整理]

工欲善其事,必先利其器.python是解释型的语言,但是在windows下如果要执行程序的话还得加个python shell的话,未免也太麻烦了.而这里所说的东西就是将pytho...

Python中*args和**kwargs的区别详解

一、*args的使用方法 *args 用来将参数打包成tuple给函数体调用 def args_test(x, y, *args): print(x, y, args) arg...