python判断数字是否是超级素数幂
作者：冬日新雨 发布时间：2023-12-24 06:16:31
标签：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)
来源：https://blog.csdn.net/dongrixinyu/article/details/78737849
0
投稿猜你喜欢
- 一 前言前一段时间接二连三的出现开发人员在测试环境和生产误操作导致数据库误删除/更新，对DBA而言，回滚数据着实是一件头疼的事情，凡涉及到恢
- 一、 collections 中 defaultdict 的使用1.字典的键映射多个值将下面的列表转成字典l = [('a'
一场大雪，覆盖了华北、华东。天地连成一片，城市银装素裹，处处诗情画意、人人兴高采烈。朋友圈被雪景图和调侃路滑摔跤的段子刷屏，气氛比过年还要热- 1. fixture的声明我们使用@pytest.fixture()来声明fixture函数。fixture()即可无参数进行声明，也可以带
- RSS 是一个可用多种扩展来表示的缩写：“RDF 站点摘要（RDF Site Summary）”、“真正简单的辛迪加（Really Simp
- 解决方法： 1。 改表法。 可能是你的帐号不允许从远程登陆，只能在localhost。这个时候只要在localhost的那台电脑，登入mys
- 简介：with是从Python2.5引入的一个新的语法，它是一种上下文管理协议，目的在于从流程图中把 try,except 和finally
- Socket是网络编程的一个抽象概念。通常我们用一个Socket表示“打开了一个网络链接”，而打开一个Socket需要知道目标计算机的IP地
- 本文实例为大家分享了Python函数式编程实现登录注册功能的具体代码，供大家参考，具体内容如下代码：def login(username,
- 1、引言小 * 丝：鱼哥，鱼哥，help…小鱼：呼吸声越来越弱，你这是劳累过度？？小 * 丝：拉倒吧，我这是激动的小鱼：什么大
- <style> body {margin:10px;background-color:#ffffff;margin-t
- 本文实例为大家分享了JavaScript实现扫雷小游戏的具体代码，供大家参考，具体内容如下工具：Sublime Text / Dreamwe
- asyncio 的一个好处是我们可以同时运行许多协程。这些协同程序可以在一个组中创建并存储，然后同时一起执行。这可以使用 asyncio.g
- 本文实例展示了Python生成日历的实现方法。该实例可实现一个月的日历生成5x7的列表，列表里的没个日期为datetime类型，采用pyth
- 来一个简单的例子，看Python如何操作数据库，相比Java的JDBC来说，确实非常简单，省去了很多复杂的重复工作，只关心数据的获取与操作。
- create or replace PROCEDURE proceudre_name AS BEGIN DECLARE sPara VARC
- 昨天发现程序中数据分析的结果不对，重新进行分析后，原数据仍在，有值的字段被累计。心说，不对啊，是重新生成记录后才分析的啊。难道忘了DELET
- /**//// <summary> /// 生成带CDATA的节点 /// </summary> /// <p
- 今天研究了下Python中的传值问题，通常在C、C++中有按值传递和按引用传递两种情况，按值传递时会拷贝实参，而按引用传递时只是给形参赋了一
- 今天学习php，当然是要先安装好运行环境了，phpstyudy是一个运行php的集成环境， 一键安装对新手很友好，与时作为一个新手，便跟着教
