一、质数定义及判断

1. 定义

定义在大于1 的数中，因数只有1 和它本身的数被成为质数。

2. 质数的基础判断

输入一个数x,判断它是不是一个质数；
一个数除以比它一半还大的数一定是除不尽的，即n的因子除了本身，最大只会到x/2;

  1. bool is_prime(int x){
  2.      if(x == 1 || x == 0) return false;
  3.     int tmp = x / 2; // 把范围缩小到 x / 2
  4.     for(int i = 2; i <= tmp; i++){
  5.          if(x % i == 0)    return false;   
  6.     }
  7.     return true;
  8. }

进一步优化范围：
如果一个数存在除了1和本身以外的两个因数，那么一定是其中一个小于等于√x，一个大于等于√x，不存在两个因数同时大于√x。那么我们从2枚举到√x，必定先找到小的因数，不需要再枚举到另一个因数。

100 = 2 50 = 5 20 = 10 * 10

  1. bool is_prime(int x){
  2.      if(x == 1 || x == 0) return false;
  3.     int tmp = sqrt(x); // 把范围缩小到 sqrt(), 头文件：cmath
  4.     for(int i = 2; i <= tmp; i++){
  5.          if(x % i == 0)    return false;   
  6.     }
  7.     return true;
  8. }

二、求 n 范围内质数个数

1. 暴力枚举法

  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  5. int n, cnt = 0;
  7. bool is_prime(int x){
  8.      if(x == 1 || x == 0) return false;
  9.     int tmp = sqrt(x); // 把范围缩小到 sqrt(), 头文件：cmath
  10.     for(int i = 2; i <= tmp; i++){
  11.          if(x % i == 0)    return false;   
  12.     }
  13.     return true;
  14. }
  16. int main(){
  17.     cin >> n;
  18.     for(int i = 1; i <= n; i++){
  19.           if(is_prime(i))    cnt++;
  20.     }
  22.     cout << cnt << endl; // n 范围内质数的个数
  24.      return 0;   
  25. }

2. 埃氏筛

埃拉托色尼选筛法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法。

基本原理：一个合数总是可以分解成若干个质数的乘积，那么如果把质数（最初只知道2是质数）的倍数都去掉，剩下的就是质数了。

时间复杂度：O(nloglogn)

  1. bool is_prime[N];
  2. int prime[N];
  4. int Get_prime(){
  5.     int cnt = 0;
  6.     memset(is_prime, true, sizeof(is_prime)); // 头文件 cstring
  7.     for(int i = 2; i <= n; i++){
  8.          if(is_prime[i]){
  9.              prime[++cnt] = i;
  10.             for(int j = i + i; j <= n; j++){
  11.                  is_prime[j] = false;   
  12.             }
  13.         }
  14.     }
  15.     return cnt; // n 范围内质数个数 cnt
  16. }

埃氏筛法做了很多无用功：对于一个合数，有可能被筛多次，例如：30 = 2 15 = 3 10 = 5 * 6

3. 欧拉筛

算法原理：规定每个合数只会被它最小的质因数筛去。

时间复杂度：O(n)

image.png
观察上表，不难发现：这里不是用 i 的倍数消去合数，而是把prime里面保存的素数，升序来当做要消去合数的最小质因子。

例如：当i == 4时，只能消去8，而不能消去12，因为12 = 43 = 62，所以12要到i == 6时才被消去。

  1. bool is_prime[N];
  2. int prime[N];
  4. int Get_prime(){
  5.     int cnt = 0;
  6.     memset(is_prime, true, sizeof(is_prime)); // 头文件 cstring
  7.     for(int i = 2; i <= n; i++){
  8.          if(is_prime[i]){
  9.              prime[++cnt] = i;
  10.         }
  11.         for(int j = 1; j <= cnt; j++){
  12.             if(i * prime[j] > n) break;  
  13.             is_prime[i * prime[j]] = false;
  14.             if(i % prime[j] == 0)    break;
  15.         }
  16.     }
  17.     return cnt; // n 范围内质数个数 cnt
  18. }