如何很快判断质数?最好用短除法,我看他们,用短除法除以一个数,很快就能判断出来
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/17 21:13:18
![如何很快判断质数?最好用短除法,我看他们,用短除法除以一个数,很快就能判断出来](/uploads/image/z/3503451-3-1.jpg?t=%E5%A6%82%E4%BD%95%E5%BE%88%E5%BF%AB%E5%88%A4%E6%96%AD%E8%B4%A8%E6%95%B0%3F%E6%9C%80%E5%A5%BD%E7%94%A8%E7%9F%AD%E9%99%A4%E6%B3%95%2C%E6%88%91%E7%9C%8B%E4%BB%96%E4%BB%AC%2C%E7%94%A8%E7%9F%AD%E9%99%A4%E6%B3%95%E9%99%A4%E4%BB%A5%E4%B8%80%E4%B8%AA%E6%95%B0%2C%E5%BE%88%E5%BF%AB%E5%B0%B1%E8%83%BD%E5%88%A4%E6%96%AD%E5%87%BA%E6%9D%A5)
如何很快判断质数?最好用短除法,我看他们,用短除法除以一个数,很快就能判断出来
如何很快判断质数?
最好用短除法,我看他们,用短除法除以一个数,很快就能判断出来
如何很快判断质数?最好用短除法,我看他们,用短除法除以一个数,很快就能判断出来
设一个数为p,
埃拉托斯特尼筛法:先对这个数p开方(√p),然后对这个开出来的数取整数部分( [√p] ),然后,用小于等于这个整数[√p]的所有素数去除这个整数p,如果皆不能整除,则这个素为素数.证明很简单,从略.
威尔逊定理:p为素数时,当且仅当( p -2)!≡ 1 ( mod p ) .也就是说,如果对于一个数p,从p-2乘以p-3乘以p-4一直乘到1,得到的数除以p余数为1,即【(p-2)*(p-3)*(p-4)……*2*1 / p余1】那么p就一定是素数,相反,如果p是素数,那么余数就一定为1.
证明很简单,从略.
我们老师是让我们背的
只能被1和本身整除的数就是质数