质数
又称:素数、prime
质数(也叫素数)是只有 1 和它本身两个正因数的、大于 1 的整数,比如 2、3、5、7、11、97。与之相对的是合数——除了 1 和自身还有别的因数,比如 91 = 7 × 13 就是合数。要特别记住两个边界:1 既不是质数也不是合数(它只有一个因数),2 是唯一的偶质数。
怎么判断一个数是不是质数?最直接的是试除法:看有没有比 1 大、比它小的数能整除它。关键优化是——只需要试到它的平方根为止。因为如果 n = a × b 且 a ≤ b,那么较小的那个因数 a 必然 ≤ √n;换句话说,一个合数的两个因数不可能都大于 √n。所以只要 √n 以内没找到因数,n 就是质数。以 97 为例,√97 ≈ 9.85,只需试除 2、3、5、7,都除不尽,所以 97 是质数。
质数为什么重要?它们是整数世界的「原子」——不能再被分解,而所有大于 1 的整数都能由质数相乘得到。现代密码学(如银行、网购用的 RSA 加密)正是建立在「把两个大质数相乘很容易、但把乘积反过来分解成质数极难」这个事实上。质数有无穷多个,但越往后越稀疏,寻找超大质数至今仍是数学和计算领域的挑战。