验证是否是素数的函数

数学界中1既是质数也不是合数

  1. bool is_prime(int num) {
  2.     if (num < 2) {
  3.         return  false; // 1不是素数
  4.     } else if (num == 2) {
  5.         return true; // 2是素数
  6.     } else if (num % 2 == 0) {
  7.         return false; // 偶数不是素数
  8.     }
  9.     for (int i = 3; i*i <= num; i+=2) { // 从3开始每+2检验num是否可以整除
  10.         if (num % i == 0) {
  11.             return false;
  12.         }
  13.     }
  14.     return true;
  15. }

因为 根号n * 根号n = n，所以 n 的素因子有一个大于根号n的自然数，则必有一个小于根号n的素因子，因此只要验证小于根号n的数能否整除即可，如果小于根号n没有那么大于根号n肯定也没有。

爱拉陶斯芬筛法

  1. int main () {
  2.     int n;
  3.     std::cin >> n;
  4.     std::vector<bool> pr(n + 1, true);
  5.     pr[1] = false;
  6.     for (int i = 2; i*i < n; ++i) {  // 从2开始将2的倍数全筛掉，从3开始将3的倍数全筛掉
  7.         if (pr[i]) {                 // 因为int ij = i*i，所以只要i*i < n即可
  8.             for (int ij = i*i; ij <= n; ij += i) {  // 初始值为i*i，因为2*i已经被2筛过
  9.                 pr[ij] = false;                     // 优化前为 2*i
  10.             }
  11.         }
  12.     }
  14.     for (int i = 2; i <= n; ++i) { // 打印
  15.         if (pr[i]) std::cout << i << std::endl;
  16.     }
  17. }
  1. 划去2的倍数；（22，23，24，25……）
  2. 划去3的倍数；（32，33，34，35，3*6……）
  3. 划去4的倍数；
  4. 划去5的倍数；
  5. 划去6的倍数；
  6. 划去7的倍数；
  7. ……

值得我们注意的是两个乘数的选择，假设我们要筛出50以内的素数，那么第一个乘数是否需要遍历 2 至 50，如果不需要范围是多少？第二个乘数的初始值是多少？

第一个乘数：
一个合数必然是 2-√n，√n-n 两个区间内的因子的乘积，那么第一个乘数只需要在 2-√n 区间内遍历素数即可，如果一个数没有在这个区间内被筛掉那么它一定不可能在 √n-n 被筛掉，否则就大于 n 矛盾了。

第二个乘数：
初始值不需要每次都从 2 开始，因为第一个乘数已经将 2 的倍数全部筛去了，同理 3 …… 初始值设置为第一个乘数。