Skip to content Skip to footer

质数判断器

质数(素数)是指在大于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是质数