算法中的数学：质数（素数）

1.质数

1.1界说

一个大于1的天然数，除了1和它自身外，不能被其他天然数整除，那么他就是质数，否则他就是合数。
注意：1既不是质数也不是合数
唯一的偶质数是2，别的所有质数都是奇质数
1.2质数判定求法

试除法：
若n为1，阐明不是质数，
若n不为1，
我们从2开始遍历到n-1，判定2到n-1是否可以被n整除，假如恣意（2，n-1）的数可以被整除，那么他就不是质数。假如都不能被整除，那么就是质数

---

上面的试除法着实还不敷好，由于必要遍历的次数靠近n次，而我们着实可以再剪掉一部分数不消判定。
结论：只要遍历从2到根号n的天然数
讲解：

若n有一个大于根号n的因数，那么它肯定有一个小于根号n的因数（由于如许两个因数相乘才会等于n）
而一个合数肯定有一个因数小于等于根号n，以是我们只要判定从2到根号n的天然数是否有关于n的因数就可以知道该数是合数照旧质数了
若存在一个可以整除的数i，那么这个数n就是合数，否则他就不是合数，而是质数
代码实现：

2. bool isprime(int num)
3. {
4.    if(num == 1) return false;
5.    for(int i = 2; i <= num/i; i++)
6.   {
7.        if(num%i == 0)
8.     {
9.        return false;
10.     }
11.   }
12. return true;
13. }

复制代码

2.更多应用方法

若我们想知道区间（1，n）中一共有多少个素数，且想知道第k个素数是谁。应该怎样求？
暴力解法：遍历判定（1，n），用全局变量count纪录一共出现的素数个数，用数组f[k]纪录第k个素数是谁
不外我们着实有其他更好的解法可以用，接下来我们分别先容

---

注意：区间肯定要是从1或2开始的一连区间才可以用反面的方法
2.1埃氏筛

 对于一个大于1的正整数，他的k倍肯定是一个合数
以是我们在访问到当前数num的时间就可以趁便把他的所有倍数剪枝掉，他的所有倍数肯定不是素数
而假如我们是从i==2开始遍历的，只要我们可以访问到的数就肯定是质数，这可以用反证法推导。
图示剖析前三轮：

被框柱的就是判定为素数的，被划掉的体现颠末倍数筛查将这些合数筛掉了，我们看到这里着实有一些数被筛掉了两次，这是由于他们是某些质数的公倍数，而我们着实可以通过优化让我们在筛查的时间减少重复筛
优化：
我们在倍数筛查的时间可以直接从i的i倍开始，由于i的2倍到i-1倍都被前面的质数倍数筛掉了
代码实现：

2. typedef long long ll;
3. const int N = 1e9;
4. bool f[N];
5. int a[N];
6. int count;
7. void get_prime(int n)
8. {
9.    for(int i = 2; i <= n; i++)
10.     {
11.        if(f[i] == true)
12.         {
13.          continue;
14.         }
15.        a[++count] =  i;
16.        for(ll j = i*i ; j <= n; j+=i)
17.         {
18.           f[j] = true;
19.         }
20.     }
21. }

复制代码

2.2线性筛

 由于埃氏筛纵然颠末从i乘i开始的优化，仍旧会有合数被重复筛，时间复杂度并不是O（n）级别。
为了使筛选的时间复杂度低沉为O（n）级别，我们必要利用线性筛

---

线性筛最多只会对每个元素访问两次，一次是遍历到的时间，一次是筛掉的时间。
核心逻辑：让每个合数被其最小质因数筛掉
代码实现核心逻辑：
从前以后遍历数i，用i的质数倍去筛，当i是当前的质数的倍数时，举行完当前筛查后制止
代码实现：
 

2. typedef long long ll;
3. const int N = 1e9;
4. bool f[N];
5. int a[N];
6. int count;
7. void get_prime(int n)
8. {
9.    for(ll i = 2; i <= n; i++)
10.     {
11. //没有被标记为true，说明是质数
12.        if(f[i] == false)
13.        {
14.          a[++count] = i;
15.        }
16. //进行线性筛
17.         for(int j = 1; i*a[j] <= n; j++)
18.        {
19.          f[i*a[j]] = true;
20.          if(i % a[j] == 0) break;
21.        {         
22.     }
23. }

复制代码

注意：
1.假如i是合数，那么他会枚举到最小质因数退却出循环；假如i是质数，那么他会枚举到等于它本身的质数退却出循环。
而这个特性表明：p[j]就是i的最小质因数
2.线性筛的for循环条件中没有j<=count是由于当j==count的时间，i==p[j]，直接break了
2.3例题讲解

审题：
本题必要我们找出区间l到r之间的所有素数的个数
思绪：
方法一：暴力解法
我们用双层for循环，外层for循环将l到r遍历，内层将1~根i的数与外层的数依次试除，然后如有一次成功整除则i为素数，count++。
时间上：外层为1e6,内层为1e6，以是统共的运行次数大概会到达1e12，会超时
方法二:二次筛选
我们着实不消将1到r的所有素数都选出来，而是只要遍历到根号r即可将1到r的素数筛选出来。
然后我们的筛选方法不消试除法，由于该方法要对每一个数都举行n次，以是利用埃氏筛。

第一步：将1到根号r的质数筛选出来
第二步：利用筛选出来的质数再利用埃氏筛的方法筛选出l到r之间的素数
第三步：纪录区间素数个数并输出

注意：
1.筛选1到根号r的素数的目的是利用埃氏筛举行l到r的筛选
2.怎样确定质数的起始倍数？
由于我们的l不是从1或2开始的，以是质数的较低倍数大概会小于l，我们为了制止这种无效筛选就要找到质数合适的起始倍数。
而该质数乘上起始倍数肯定要大于等于l的值
于是我们得出以下向上取整的倍数计算式:   l+x-1/x
剖析：本来l/x就可以大概得到所需倍数，但是大概由于被计算机向下取整导致计算效果仍小于l，以是我们在分子加上x-1就举行了向上取整的操作

解题：
 

2. #include<iostream>
3. #include<cmath>
4. using namespace std;
5. typedef long long ll;
6. const int N = 1e6 + 10;
7. ll l, r;
8. int cou;//记录1~根号r的素数个数
9. ll prime[N];//记录素数
10. bool f[N];//埃氏筛筛查表
11. bool F[N];
12. void selprime()
13. {
14.        
15.         for (ll i = 2; i <= sqrt(r); i++)
16.         {
17.                 if (F[i] == true)//被筛掉了
18.                 {
19.                         continue;
20.                 }
21.                 else
22.                 {
23.                         prime[cou++] = i;
24.                         ll j = i;
25.                         while (j * i <= sqrt(r))//进行标记
26.                         {
27.                                 F[j * i] = true;
28.                                 j++;
29.                         }
30.                 }
31.         }
32. }
33. int main()
34. {
35.         cin >> l >> r;
36.         l = l == 1 ? 2 : l;//控制l不为1
37.         //筛选1~根号r的素数
38.         selprime();
39.         //利用埃氏筛和选出的素数对l到r区域进行筛选
40.         for (int i = 0; i < cou; i++)
41.         {
42.                 ll x = prime[i];
43.                 for (ll j = max(2 * x, (l + x - 1) / x * x); j <= r; j += x)
44.                 {
45.                         f[j-l] = true;
46.                 }
47.         }
48.         //记录区间素数个数
49.         ll count = 0;
50.         for (ll i = l; i <= r; i++)
51.         {
52.                 if (f[i-l] == false)
53.                         count++;
54.         }
55.         cout << count << endl;
56.         return 0;
57. }

复制代码

1.我们的第一次筛选利用的是埃氏筛，以是利用了一个F数组来纪录筛选效果。
2.由于1既不是合数也不是素数，以是我们将l为1的情况变为l为2
3.若出现l的值和筛选出的质数的值一样的情况，也就是起始倍数为1，我们不能对它打上true标记，由于他是质数，以是我们加一个判定，若倍数为1则将倍数设置为2举行筛选
4.由于l和r的数据范围较大，为了合法纪录筛选情况，我们不能直接用f[j]纪录情况，而是要将j情况映射到j-l处，由于l和r之间的差小于1e6，我们是可以纪录的