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 构造三维全零数组的方法

如下所示: temp1 = [[] for i in range(10)] temp2 = [temp1 for i in range(20)] temp3 = [temp2 for...

Python contextlib模块使用示例

看这个模块要先看with as的用法,最常用的方法就是打开一个文件: 复制代码 代码如下: with open(“filename”) as f: f.read() with可以调用一...

python实现图片处理和特征提取详解

python实现图片处理和特征提取详解

这是一张灵异事件图。。。开个玩笑,这就是一张普通的图片。 毫无疑问,上面的那副图画看起来像一幅电脑背景图片。这些都归功于我的妹妹,她能够将一些看上去奇怪的东西变得十分吸引眼球。然而,我...

用pandas中的DataFrame时选取行或列的方法

如下所示: import numpy as np import pandas as pd from pandas import Sereis, DataFrame ser = Ser...

python实现汉诺塔算法

题目: 汉诺塔给出最优解,如果对汉诺塔的定义有不了解,请翻看数据结构教材。 除了最基本的之外,还有一题,给定一个数组,arr=[2,3,1,2,3],其含义是这是一个有5个圆盘的汉诺塔...