一：判定质数以及分解质因数
1.试除法判定质数O（sqrt（n））：
质数是除1和本身以外，不能被任何数整除的数。
试除法判定 m 是否为质数的过程：
1.先特判 m==2 和 1 的情况
2. for 循环从 i = 2 遍历到 m / i ，如果期间有 i 能整除 m ，则不是质数。如果循环结束了，则证明m是质数。
为什么遍历到m/i，而不是m：
因为24=2*12，循环到2的时候已经可以判断24不是质数，没必要再循环到12。（节省时间）
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 bool isprimes(int m)
5 {
6 if(m==2)return 1;
7 if(m==1)return 0;
8 for(int i=2;i<=m/i;i++)
9 {
10 if(m%i==0)return 0;
11 }
12 return 1;
13 }
14
15 int main()
16 {
17 int n;
18 cin>>n;
19 for(int i=1;i<=n;i++)
20 {
21 int m;
22 cin>>m;
23 if(isprimes(m))puts("Yes");
24 else puts("No");
25 }
26
27
28 return 0;
29 }
试除法判定质数
2.六倍筛法O（sqrt（n）/3）：
1 bool Is_prime(int n)
2 {
3 if(n==1) return false;
4 if(n==2||n==3) return true;
5 if(n%6!=1&&n%6!=5) return false;
6 for(register int i=5;i*i<=n;i+=6)
7 if(n%i==0||n%(i+2)==0) return false;
8 return true;
9 }
六倍筛法
3.试除法分解质因数：
质因数定义：质因数（素因数或质因子）在数论里是指能整除给定正整数的质数。
正整数的因数分解可将正整数表示为一连串的质因子相乘（ 如8 = 2 * 2 * 2 ）
试除法分解质因数过程：
1.特判m==1的情况
2.for循环从2到m/i，期间如果有i能整除m，就while循环求出m能整除i的几次方，过程中就是在不断分解m
3.循环结束后，如果m>1，则单独输出m （比如7）
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 void divide(int m)
5 {
6 if(m==1)cout<<m<<" "<<m<<endl;
7 for(int i=2;i<=m/i;i++)
8 {
9 if(m%i==0)
10 {
11 int cnt=0;
12 while(m%i==0)
13 {
14 cnt++;
15 m/=i;
16 }
17 if(cnt)cout<<i<<" "<<cnt<<endl;
18 }
19 }
20 if(m>1)cout<<m<<" 1"<<endl;
21 puts("");
22 }
23
24 int main()
25 {
26 int n;
27 cin>>n;
28 for(int i=1;i<=n;i++)
29 {
30 int m;
31 cin>>m;
32 divide(m);
33 }
34
35
36
37 return 0;
38 }
试除法分解质因数
二：各种质数筛
1.埃氏质数筛法O(nloglogn)：
核心思想：只枚举质数的倍数
埃氏质数筛的过程：
1.特判m==1
2.for循环从2遍历到m
如果st [ i ] 为0（说明 i 是质数），cnt++（计数）
for循环 j 从 i 到小于 m 的值，进制为 i 的乘数，将 j 标记 st [ j ] = 1（ i 的倍数都不是质数，直接排除）
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N=1e6+100;
5 int primes[N],cnt;
6 bool st[N];
7 void get_primes(int m)
8 {
9 if(m==1)cnt=0;
10 for(int i=2;i<=m;i++)
11 {
12 if(!st[i])
13 {
14 primes[cnt++]=i;
15 for(int j=i*2;j<=m;j+=i)st[j]=1;
16 }
17
18 }
19
20 }
21
22 int main()
23 {
24 int n;
25 cin>>n;
26 get_primes(n);
27 cout<<cnt<<endl;
28
29
30
31 return 0;
32 }
埃氏筛
2.欧拉筛O(n)：
核心思想：让每个合数只被最小质因数筛
关键点：
for(int j=0;primes[j]<=m/i;j++)
{
st[primes[j]*i]=1;
if(i%primes[j]==0)break;
}
1.当i%primes [ j ]==0时，证明primes [ j ]是i的最小质因数，那么pj也是i*pj的最小质因数
2.当i%primes [ j ]！=0时，证明primes [ j ]小于i的最小质因数，但pj仍是i*pj的最小质因数
根据1和2得：无论pj是否能整除i，pj都是i*pj得最小质因数，而欧拉筛就是利用最小质因数来筛掉合数的，所以当循环到pj时，pj就是pj*i的最小质因数，一定会把pj*i给筛掉
就是st[primes[j]*i]=1;这一步啦
3.因为欧拉筛利用的是最小质因数筛掉合数，且for循环是递增的，所以当i能被pj整除说明pj就是i的最小质因数，而p [ j + 1 ]就大于i的最小质因数了，不应该循环到这一步。
就是if(i%primes[j]==0)break;这一步啦
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N=1e6+100;
5 int primes[N],cnt;
6 bool st[N];
7 void get_primes(int m)
8 {
9 if(m==1)cnt=0;
10 for(int i=2;i<=m;i++)
11 {
12 if(!st[i])primes[cnt++]=i;
13 for(int j=0;primes[j]<=m/i;j++)
14 {
15 st[primes[j]*i]=1;
16 if(i%primes[j]==0)break;
17 }
18
19 }
20
21 }
22
23 int main()
24 {
25 int n;
26 cin>>n;
27 get_primes(n);
28 cout<<cnt<<endl;
29
30
31
32 return 0;
33 }
欧拉筛