作业帮如何很快判断质数?最好用短除法,我看他们,用短除法除以一个数,很快就能判断出来
来源：学生作业帮 编辑：作业帮 分类：数学作业 时间：2024/05/05 19:28:42
如何很快判断质数?
最好用短除法,我看他们,用短除法除以一个数,很快就能判断出来
最好用短除法,我看他们,用短除法除以一个数,很快就能判断出来
设一个数为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.
证明很简单,从略.
埃拉托斯特尼筛法：先对这个数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.
证明很简单,从略.