为什么只需要验证到平方根就够了
如果一个数n存在一个大于√n的因数,那么它必然会和一个小于√n的因数配对,因为n的因数总是成对出现、两两相乘等于n。因此只要把候选因数验证到√n(包含√n本身)为止,只要存在因数就一定会被发现,这比一直验证到n本身要快得多。
质数为什么在数学课之外也很重要
现代的加密系统,包括广泛用于保护网络通信安全的RSA算法,都依赖于这样一个特性:把两个很大的质数相乘很容易,但如果不事先知道是哪两个质数,想把相乘得到的这个大数重新分解回原来的质因数,却极其困难。这种不对称性,正是互联网安全很大一部分所依赖的数学基础。
常见问题
1是质数吗?
不是。质数必须恰好有两个不同的正因数,而1只有一个因数(它本身),所以即使在日常语感里它看起来"不太好被分解",也并不满足质数的定义。
手算判断一个数是不是质数,最快的方法是什么?
先排除大于2的所有偶数,然后只验证奇数因数,一直验证到这个数的平方根为止就可以停止。这样可以省去逐一验证每个数这种笨方法所需要的大部分不必要的计算。