109541是质数还是合数,怎样快速判断?不要穷举法和计算机算法你所提到的算法能给我简单介绍一下吗？

来源：学生作业帮助网 编辑：作业帮 时间：2024/05/10 19:21:28
109541是质数还是合数,怎样快速判断?不要穷举法和计算机算法你所提到的算法能给我简单介绍一下吗？

109541是质数还是合数,怎样快速判断?不要穷举法和计算机算法你所提到的算法能给我简单介绍一下吗？
109541是质数还是合数,怎样快速判断?
不要穷举法和计算机算法
你所提到的算法能给我简单介绍一下吗？

109541是质数还是合数,怎样快速判断?不要穷举法和计算机算法你所提到的算法能给我简单介绍一下吗？
是质数.
我是学计算机的,目前在此行业判断质数还是要靠大量的计算的,不过利用算法,可以大大的减少计算的次数.如果有其他快速的判断方法,那密码界的某个加密算法就要面临淘汰了.
一个简单的算法就是遍历,从2开始到SQRT(要判断的数),看有没有约数.
另一个是在学网络信息安全时学的一个算法,挺复杂的,RSA加密算法的一部分,它在进行s次运算后,能判断一个数是质数的准确率达到1－1/(2^S).想想吧,当S=10,这个概率就是99.999％.
判断的依据是：
命题;如果一个数p是素数,则方程：
X^2=1 mod p只有平凡解即：X=＋－1 mod p
证明：
X^2=1 mod p
->p|(X^2-1) |表示整除
->P|(X-1)(X+1)
->P|(X-1)或P|(X+1)
->X+1=KP 或 X-1=JP
->X=1 MOD P 或X= -1 MOD P
如果需要算法,可以看Miller and Rabin,WITNESS算法.

怎样快速判断是质数还是合数? 怎样快速的算出一个数是否是质数?想问问如果想15487的这种数,如何快速判断出是质数还是合数呢? 109541是质数还是合数,怎样快速判断?不要穷举法和计算机算法你所提到的算法能给我简单介绍一下吗？ 怎样判断一个数是质数还是合数? 怎样判断一个数是质数还是合数? 怎么快速看出是质数还是合数? 怎样才能非常快速地判断一个数是质数还是合数?小学五年级水平. 如何判断269是质数还是合数 197是质数还是合数,怎么判断 判断277.437是质数还是合数 判断223,431是质数还是合数? 判断277.437是质数还是合数 判断437,541是质数还是合数. 判断223,431是质数还是合数? 如何快速分辨一大数是质数还是合数 质数和合数如何快速判断帮个忙啦. 断33333633333是质数还是合数?判断4444445111111是质数还是合数? 怎样快速地分辨合数和质数