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画出三角形外接圆和内切圆的方法

python画出三角形外接圆和内切圆的方法

刚看了《最强大脑》中英对决,其中难度最大的项目需要选手先脑补泰森多边形,再找出完全相同的两个泰森多边形。在惊呆且感叹自身头脑愚笨的同时,不免手痒想要借助电脑弄个图出来看看,闲来无事吹吹牛...

Python numpy线性代数用法实例解析

Python numpy线性代数用法实例解析

这篇文章主要介绍了Python numpy线性代数用法实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 numpy中线性代数用法...

python基础入门学习笔记(Python环境搭建)

python基础入门学习笔记(Python环境搭建)

Python学习第一篇。把之前学习的Python基础知识总结一下。 一、认识Python 首先我们得清楚这个:Python这个名字是从Monty Python借鉴过来的,而不是源于大家所...

使用Tensorflow将自己的数据分割成batch训练实例

使用Tensorflow将自己的数据分割成batch训练实例

学习神经网络的时候,网上的数据集已经分割成了batch,训练的时候直接使用batch.next()就可以获取batch,但是有的时候需要使用自己的数据集,然而自己的数据集不是batch形...

Linux下通过python获取本机ip方法示例

Linux下通过python获取本机ip方法示例

下面介绍在Linux上利用python获取本机ip的方法. 经过网上调查, 发现大致有两种方法, 一种是调用shell脚本,另一种是利用python中的socket等模块来得到,下面是这...