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

2024-10-02 05:18:40

如果一个数字能表示成 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实现求最大公约数及判断素数的方法.分享给大家供大家参考.具体实现方法如下: #!/usr/bin/env python def showMaxFactor(num): count = num / 2 while count > 1: if num % count == 0: print 'largest factor of %d is %d' % (num, count) break #break跳出时会跳出下面的else语句 count -= 1 else: prin
使用Python判断质数(素数)的简单方法讲解

质数又称素数.指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数.素数在数论中有着很重要的地位.比1大但不是素数的数称为合数.1和0既非素数也非合数.质数是与合数相对立的两个概念,二者构成了数论当中最基础的定义之一.基于质数定义的基础之上而建立的问题有很多世界级的难题,如哥德巴赫猜想等.算术基本定理证明每个大于1的正整数都可以写成素数的乘积,并且这种乘积的形式是唯一的.这个定理的重要一点是,将1排斥在素数集合以外.如果1被认为是素数,那么这些严格的阐述就不得不加上一些限制条
Python实现输出某区间范围内全部素数的方法

本文实例讲述了Python实现输出某区间范围内全部素数的方法.分享给大家供大家参考,具体如下: # -*- coding: utf-8 -*- # 简述:区间范围101-200 # 要求:判断这个区间内有多少个素数,并逐一输出. def prime(m,n): list1=[] list2=[] for i in range(m,n+1): list1.append(i) for j in range(2,m/2): if i%j==0: list2.append(i) break #print
Python实现高效求解素数代码实例

素数是编程中经常需要用到的. 作为学习Python的示例,下面是一个高效求解一个范围内的素数的程序,不需要使用除法或者求模运算. #coding:utf-8 #设置python文件的编码为utf-8,这样就可以写入中文注释 def primeRange(n): myArray=[1 for x in range(n+1)] ##列表解析,生成长度为(n+1)的列表,每个数值都为1 myArray[0]=0 myArray[1]=0 startPos=2 while startPos <= n:
Python编程判断一个正整数是否为素数的方法

本文实例讲述了Python编程判断一个正整数是否为素数的方法.分享给大家供大家参考,具体如下: import string import math #判断是否素数的函数 def isPrime(n): if(n<2): return False; elif(n==2): return True; elif(n>2): for d in range(2,int(math.ceil(math.sqrt(n))+1)): if(n%d==0): return False; return True;
Python求出0~100以内的所有素数

质数又称素数.一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数:否则称为合数. 一.判断一个数是否为素数: 基于定义 def is_prime(num): if num <= 1: return '%d是一个合数' % num for i in range(2, num): if not num % i: return '%d是一个合数' % num else: return '%d是一个素数' % num 考虑合数的性质 def is_prime(num): if num
Python素数检测实例分析

本文实例讲述了Python素数检测的方法.分享给大家供大家参考.具体如下: 该程序实现了素数检测器功能,如果结果是true,则是素数,如果结果是false,则不是素数. def fnPrime(n): for i in range(2,n,1): if(n % i == 0): return bool(0) return bool(1) 希望本文所述对大家的Python程序设计有所帮助.
python求素数示例分享

复制代码代码如下: # 判断是否是素数def is_sushu(num): res=True for x in range(2,num-1): if num%x==0: res=False return res return res # 打印出素数列表print ([x for x in range(1000) if is_sushu(x)])
Python素数检测的方法

本文实例讲述了Python素数检测的方法.分享给大家供大家参考.具体如下: 因子检测: 检测因子,时间复杂度O(n^(1/2)) def is_prime(n): if n < 2: return False for i in xrange(2, int(n**0.5+1)): if n%i == 0: return False return True 费马小定理: 如果n是一个素数,a是小于n的任意正整数,那么a的n次方与a模n同余实现方法: 选择一个底数(例如2),对于大整数p,如果2^(
Python 判断是否为质数或素数的实例

一个大于1的自然数,除了1和它本身外,不能被其他自然数(质数)整除(2, 3, 5, 7等),换句话说就是该数除了1和它本身以外不再有其他的因数. 首先我们来第一个传统的判断思路: def handlerNum(num): # 质数大于 1 if num > 1: # 查看是否有其他因子 for i in range(2, num//2+1): if (num % i) == 0: print(num,"不是质数") break else: print(num, "是质

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

相关推荐

随机推荐