python判断数字是否是超级素数幂
作者:冬日新雨 时间:2023-12-24 06:16:31
如果一个数字能表示成 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
标签:python,超级素数幂
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
python基于itchat模块实现微信防撤回
2022-03-15 01:41:42
Django + Uwsgi + Nginx 实现生产环境部署的方法
2023-01-01 06:02:49
![](https://img.aspxhome.com/file/2023/2/68982_0s.png)
Python 字符串去除空格的五种方法
2023-01-15 08:23:56
Python selenium 父子、兄弟、相邻节点定位方式详解
2023-07-03 06:19:09
利用Pycharm断点调试Python程序的方法
2023-07-05 03:47:08
![](https://img.aspxhome.com/file/2023/2/97242_0s.jpg)
python 使用openpyxl读取excel数据
2021-02-10 07:32:10
![](https://img.aspxhome.com/file/2023/0/130940_0s.png)
python实现selenium网络爬虫的方法小结
2023-01-13 03:43:38
![](https://img.aspxhome.com/file/2023/9/128199_0s.png)
MySQL8重置root账户密码图文教程超详细讲解
2024-01-25 17:40:55
![](https://img.aspxhome.com/file/2023/6/78106_0s.png)
Python如何使用带有 for 循环的 Lambda 函数
2021-05-28 05:06:05
Golang搭建开发环境的图文教程
2024-04-26 17:28:51
![](https://img.aspxhome.com/file/2023/6/134036_0s.jpg)
window.location 对象所包含的属性
2024-04-16 10:32:14
20个解决日常编程问题的Python代码分享
2021-02-14 03:57:41
![](https://img.aspxhome.com/file/2023/8/89118_0s.png)
ubuntu定时执行python脚本实例代码
2022-11-30 17:35:03
goroutine 泄漏和避免泄漏实战示例
2024-02-18 03:31:15
![](https://img.aspxhome.com/file/2023/6/105146_0s.png)
Sklearn调优之网格搜索与随机搜索原理详细分析
2022-05-11 10:47:12
TFRecord文件查看包含的所有Features代码
2023-07-26 15:45:08
Python反向传播实现线性回归步骤详细讲解
2021-06-04 10:20:03
![](https://img.aspxhome.com/file/2023/5/64285_0s.png)
详解pandas.DataFrame.plot() 画图函数
2021-06-02 21:41:49
![](https://img.aspxhome.com/file/2023/1/97301_0s.png)
玩转Python发短信的实现
2021-09-17 20:38:54
![](https://img.aspxhome.com/file/2023/1/79801_0s.jpg)
phar绕过phar与HALT实现文件上传功能
2023-05-25 06:47:36