python大数快速判断质数与分解质因数_huangpo001的博客
文章推薦指數： 80 %
此文件为python源文件，用来把输入的正整数因式分解，因式分解表达式规范。
... 【输入形式】标准输入的一行表示正整数n 【输出形式】标准输出的一行 ...
python大数快速判断质数与分解质因数
hp901123
于 2019-11-2716:25:49 发布
1712
收藏
3
分类专栏：
python
文章标签：
python
质因数分解
大数
质数
版权声明：本文为博主原创文章，遵循CC4.0BY-SA版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/huangpo001/article/details/103277632
版权
python
专栏收录该内容
6篇文章
0订阅
订阅专栏
python大数质因数分解
数字较小时：
defis_prime(number):
foriinxrange(2,int(math.sqrt(number))+2):
ifnumber%i==0andnumber!=i:
returnFalse
returnTrue
数字较大时：判断是否为质数：isPrime(num)质因数分解：factor(num)
#coding:utf-8
fromrandomimportrandint
"""
快速质因数分解
"""
defquickMulMod(a,b,m):
'''a*b%m,quick'''
ret=0
whileb:
ifb&1:
ret=(a+ret)%m
b//=2
a=(a+a)%m
returnret
defquickPowMod(a,b,m):
'''a^b%m,quick,O(logn)'''
ret=1
whileb:
ifb&1:
ret=quickMulMod(ret,a,m)
b//=2
a=quickMulMod(a,a,m)
returnret
defisPrime(n,t=5):
'''millerrabinprimalitytest,aprobabilityresult
tisthenumberofiteration(witness)
'''
t=min(n-3,t)
ifn<2:
print('[Error]:{}can\'tbeclassedwithprimeorcomposite'.format(n))
return
ifn==2:returnTrue
d=n-1
r=0
whiled%2==0:
r+=1
d//=2
tested=set()
foriinrange(t):
a=randint(2,n-2)
whileaintested:
a=randint(2,n-2)
tested.add(a)
x=quickPowMod(a,d,n)
ifx==1orx==n-1:continue#success,
forjinrange(r-1):
x=quickMulMod(x,x,n)
ifx==n-1:break
else:
returnFalse
returnTrue
defgcd(a,b):
whileb!=0:
a,b=b,a%b
returna
deffactor(n):
'''pollard'srhoalgorithm'''
ifn==1:return[]
ifisPrime(n):return[n]
fact=1
cycle_size=2
x=x_fixed=2
c=randint(1,n)
whilefact==1:
foriinrange(cycle_size):
iffact>1:break
x=(x*x+c)%n
ifx==x_fixed:
c=randint(1,n)
continue
fact=gcd(x-x_fixed,n)
cycle_size*=2
x_fixed=x
returnfactor(fact)+factor(n//fact)
hp901123
关注
关注
0
点赞
踩
0
评论
3
收藏
打赏
扫一扫，分享内容
点击复制链接
专栏目录
把正整数因式分解的python代码
01-24
此文件为python源文件，用来把输入的正整数因式分解，因式分解表达式规范。
里面含有质数的定义代码，可以用来判断输入的数字是否为质数。
如果判断输入的数字是合数，就将其因式分解。
代码不到40行，都是用最基础的代码和逻辑写的，适合初学者学习和提高逻辑思维能力。
Python实现正整数分解质因数操作示例
12-23
本文实例讲述了Python实现正整数分解质因数操作。
分享给大家供大家参考，具体如下：
遇到一个Python编程练习题目：将一个正整数分解质因数。
例如：输入90,打印出90=2*3*3*5。
#!/usr/bin/envpython
#-*-coding:utf-8-*-
defdiv_func(n):
result=[]
whileTrue:
foriinxrange(2,int(n**0.5)+1):
ifn%i==0:
result.append(i)
n/=i
bre
参与评论
您还未登录，请先
登录
后发表或查看评论
大数运算代码实现
01-16
用python编程实现大数的运算，解决了RSA算法中的大数运算问题
任意位整数质因数快速分解工具
05-06
大整数质因素快速分解理论上,大约在2~3天内可以破解96位的RSA密钥
积最大的分解（Python）
12-21
【问题描述】从键盘输入一个正整数n(n>1)，该正整数可以分解成两个正整数k1和k2之和（允许k1和k2相等）。
请编写一个函数求使两个正整数的乘积最大的分解方案，并返回乘积max。
【输入形式】标准输入的一行表示正整数n
【输出形式】标准输出的一行表示最大乘积max，若输入的数据不合法（如：负整数、0或1），输出”illegalinput”。
【样例输入】20
【样例输出】100
【样例说明】20=10+10，此时积最大，为100。
defmax_divide():
num=int(input())
ifnum<=1:
print('illeg
用Python分解质因数
热门推荐
编程笔记
04-14
1万+
思路：1.定义一个函数，判断是否是素数（利用素数定义就可以） 2.对具体的数字N，首先判断是否是素数.是程序结束，不是则利用if-else嵌套要求同时满足两个条件 （1）对属于（2，N）之间的数i，能整除N (2)i是素数 则i是n的质因数，如果i%N是质数，就不用再分解了，不是继续循环代码...
【Python】对大数质因数分解的算法问题
初雪
11-29
3161
【Python】对大数质因数分解的算法疑问前言我的代码百科代码
前言
我是一个初学者，在编写一个分解质因数的代码时，学习到了Miller-Rabin素数测试算法和Pollard-Rho算法这两个算法。
于是自己编写了一段代码（下称C1），运行后效果还不错，但感觉还可以优化，于是在网上搜索。
最后在百度百科上看到了一段代码（下称C2），同样使用了上述两个算法。
运行C2后发现，对某些数字，C2的...
python找出因数与质因数的方法
09-18
主要介绍了python找出因数与质因数的方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
python分解质因数
weixin_30670965的博客
02-14
300
将一个正整数分解质因数。
例如：输入90,打印出90=2*3*3*5。
#!/usr/bin/envpython
#-*-coding:utf-8-*-
#Author:HiuhungWan
num=input("请输入一个合数：")
ifnum.isdigit():
num=int(num)
else:
print("输入非法，请输入...
分解质因数
Algorithm攻略日记
05-16
1378
将一个正整数分解质因数。
例如：输入90,打印出90=2*3*3*5。
代码如下：#include
usingnamespacestd;
voidfactorize(intn)
{
cout<
2.余额无法直接购买下载，可以购买VIP、C币套餐、付费专栏及课程。
余额充值
延伸文章資訊
- 1Python 练习实例14 | 菜鸟教程
Python 练习实例14 Python 100例题目：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。 程序分析：对n进行分解质因数，应先找到一个最小的质数k， ...
- 2Python 質因數分解( Python: Prime Factorization ) - 雲林SONG
- 3python 将一个正整数分解质因数。例如：输入90,打印出90=2*3 ...
- 4python整数的质因数分解 - BBSMAX
算术基本定理首先,我们得知道,任意一个大于1的自然数都可以分解为有限个质数的乘积.这里因子均为质数,且为正整数.我们把这样的分解成为N的标准分解式.
- 5質因數分解- Python 教學 - STEAM 教育學習網
這篇文章會介紹使用Python 變數的計算、while 迴圈、for 迴圈、input 指令和if 判斷式，做出一個使用者輸入數字後，判斷數字是否為質數，如果不是質數，就將其做質因數 ...
