怎么快速判断一个数是质数还是合数
文章目录:
一、怎么快速判断一个数是质数还是合数
怎么快速判断一个数是质数还是合数如下:
1、定义分辨
质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。合数指自然数中除了能被1和本身整除外,还能被其他数(O除外)整除的数。数字1既不是质数也不是合数。
2、根据性质分辨
所有大于2的偶数都是合数。所有大于5的奇数中,个位为5的都是合数。除O以外,所有个位为O的自然数都是合数。所有个位为4,6,8的自然数都是合数。
质数性质特点:
质数p的约数只有两个:1和p。初等数学基本定理:任一大于1的自然数,要么本身是质数,要么可以分解为几个质数之积,且这种分解是唯一的。质数的个数是无限的。质数的个数公式π(n)是不减函数。
若n为正整数,在n到(n+1)之间至少有一个质数。若n为大于或等于2的正整数,在n到之间至少有一个质数。若质数p为不超过n(n>4)的最大质数,则p>n/2所有大于10的质数中,个位数只有1,3,7,9。
质数的应用:
质数被利用在密码学上,所谓的公钥就是将想要传递的信息在编码时加入质数,编码之后传送给收信人,任何人收到此信息后,若没有此收信人所拥有的密钥,则解密的过程中(实为寻找素数的过程),将会因为找质数的过程(分解质因数)过久,使即使取得信息也会无意义。
在汽车变速箱齿轮的设计上,相邻的两个大小齿轮齿数设计成质数,以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数,可增强耐用度减少故障。
合数的性质:
所有大于2的偶数都是合数。所有大于5的奇数中,个位为5的都是合数。除0以外,所有个位为0的自然数都是合数。所有个位为4,6,8的自然数都是合数。最小的(偶)合数为4,最小的奇合数为9。每一个合数都可以以唯一形式被写成质数的乘积,即分解质因数。
二、怎样快速地看出一个数是否为质数?(求好方法)
1 朴素筛法,就是直接试除
2 若a是n的因子,那么n/a也是n的因子,所以如果n有一个大于1的真因子,则必有一个不大于n的1/2次方的因子
3 进一步的,如n是合数,他必有一个素因子不大于n的1/2次方,如要检测一个m以内的数是否为素数需事先建立一个m的1/2次方以内素数表。
4 Miller-Rabbin算法
5 概率算法
6 无条件的素数测试(包含APR算法 Jacobi sum测试 等)
7.n的n次幂除以n,若余数为2,则n为质数
末尾是0或5的肯定不是,因为它们是5的倍数,末尾是0.2.4.6.8的肯定也不是,因为,它们是2的倍数,一个数的数字之和是3肯定也不是,因为它们是3的倍数,还有,质数除了2以外其他的都是单数
只要这数只能被它自己和1除就行
先确认那个数是不是偶数或5的倍数,如果是则是合数。
然后再分别除以3和7,如有余数,则是质数,反之,就是合数。
到此,以上就是小编对于如何快速判断一个数是否是质数的问题就介绍到这了,希望介绍关于如何快速判断一个数是否是质数的2点解答对大家有用。
Amysql_youhua_articlehuaunyuan($article);