质数(素数)是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。
例如:2, 3, 5, 7, 11, 13, 17, 19, 23, 29等。
质数的性质:
质数只有两个正因数:1和它本身
大于1的自然数,要么是质数,要么可以唯一分解为质数的乘积
2是最小的质数,也是唯一的偶数质数
质数的个数是无限的(欧几里得证明)
除了2和3,所有质数都可以表示为6n±1的形式
质数判断方法:
试除法:用小于等于√n的所有质数去试除n
费马小定理:如果p是质数,a不是p的倍数,则a^(p-1) ≡ 1 (mod p)
米勒-拉宾素性测试:一种概率性质数测试方法
使用试除法判断97是否为质数:
√97 ≈ 9.85,所以只需检查小于等于9的质数
97 ÷ 2 = 48.5(不整除)
97 ÷ 3 = 32.33(不整除)
97 ÷ 5 = 19.4(不整除)
97 ÷ 7 = 13.857(不整除)
结论:97是质数