先弄清楚我们在上小学时 学的概念。

1、什么是质因数？
     -质因数是指能够整除给定正整数的质数。每个正整数都可以被表示为几个质数的乘积，这些质数就是该数的质因数。质因数分解是将一个正整数分解成若干个质数相乘的过程。例如，数字 12 的质因数分解是 2 × 2 × 3，因此 2 和 3 是 12 的质因数。

2、什么是质因数的底数与指数？
      -底数（Base）：指的是质因数分解中的质数。这些质数是构成原数的不可再分的基本元素。例如，在质因数分解12的过程中，底数是2和3，因为12可以分解为2和3的乘积。
      -指数（Exponent）：指的是在质因数分解中，每个质因数出现的次数。指数表示该质因数在原数中的“数量”。例如，数字12可以分解为 22×3122×31，这里2的指数是2，表示质因数2出现了两次；3的指数是1，表示质因数3出现了一次。

3、什么是合数？
      -合数是一个大于1的自然数，它不是质数，也就是说，它除了1和它本身以外，至少还有一个正因数。换句话说，合数可以被分解为两个或更多较小的正整数的乘积。合数的判定方法通常是通过检查一个数是否有除了1和它本身以外的因数。如果一个数可以被除了1和它本身以外的任何数整除，那么这个数就是合数。

4、什么是因数？
      -因数是指能够整除给定正整数的数。换句话说，如果一个数b能够被另一个数a整除，那么b就是a的因数。因数通常是指除了1和它本身以外的因数，因为1是所有正整数的因数。

质数

质数的判断

在判定一个数是否为质数时常用试除法

题目：866. 试除法判定质数 - AcWing题库

代码：

复杂度是严格的O(sqrt(n))

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N=105;
int n,a[N];bool check_prime(int x)
{//1不是质数if(x<2) return false;//对于一个非质数的数而言，一定含有两个因数，所以只要枚举较小的那一个即可for(int i=2;i<=x/i;i++){if(x%i==0) return false;}return true;
}int main()
{cin >> n;for(int i=0;i<n;i++){cin >> a[i];if(check_prime(a[i])) cout << "Yes" << endl;else cout << "No" << endl;}return 0;}

这里的 判定条件写为i <= x/i 而不写成i <= sqrt(x) 的原因是因为后者效率低，不写成i*i <= x 原因是因为防止i*i时溢出

分解质因数

分解质因数——试除法（O(sqrt(n))——>O(log2(n))~O(sqrt(n))）
从小到大枚举所有数

for(int i=2;i<=n;i++)if(n%i==0){int s=0;while(n%i==0){n/=i;s++;}cout << i << s << endl;}

在这里枚举的是所有因数，而不是枚举的所有质因数。
原因就是在枚举所有数的过程中，当枚举到i的时候，2~i-1之间的i的所有因数都被除干净了
所以这里所枚举的就是质因数。例如n=8的时，i=2就会把n置于0，枚举到i=4的时候已经n已经=1了。

由于n当中最多只包含一个大于sqrt(n)的质因子，即它本身
所以代码为：

for(int i=2 ;i <= n/i;i ++ )if(n%i==0){int s=0;while(n%i==0){n/=i;s++;}cout << i << s << endl;}if(n>1) cout << n << 1 << endl;

题目：867. 分解质因数 - AcWing题库

代码：

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;int n,a[105];void print_prime(int x)
{for(int i=2;i<=x/i;i++){if(x%i==0){int s=0;//求底数的质数while(x%i==0){//这里如果质因数的质数不唯一，那么就逐个舍弃x/=i;s++;}cout << i << ' ' << s << endl;}}//经过上述质因数的分解后，x>1的话，那么x就是一个质数。比如17、19...经过上述循环仍为它本身if(x>1) cout << x  << ' ' << 1 << endl;//注意题目要求的格式cout << endl;return;
}int main()
{cin >> n;for(int i=0;i<n;i++){cin >> a[i];print_prime(a[i]);}return 0;
}

筛质数 

两种算法，

1、朴素筛法：对2~n-1的数的倍数做标记，那么剩余没有被标记的即为质数。因为剩余的也就没有因子。

贴个图，一目了然

 板子：

void get_prime(int n)
{for(int i=2;i<=n;i++){if(!st[i]){prime[res++]=n;}for(int j=i+i;j<=n;j+=i) st[j]=true;}
}

对朴素筛选的优化 ——埃氏筛 
 在筛选过程中只用质数去筛，因为一个数最小的因数就是质因数，证明：一个数的除了1之外最小的因数一定是质数吗？为什么？_百度知道 (baidu.com)

板子：

void get_prime(int n)
{for(int i=2;i<=n;i++){//如果被筛选后仍为false，则为质数if(!st[i]){res++;for(int j=2*i;j<=n;j+=i) st[j]=true;}}
}

缺点：无论怎样优化都会有数被多次标记，进而增加复杂度

2、线性筛

用每个合数只会被最小的质因数筛掉。因为每个数的最小质因数只有一个，所以每一个数只会被筛一次，所以总体为线性。

板子：

void get_prime(int n)
{for(int i=2;i<=n;i++){if(!st[i]) a[res++]=i;for(int j=0;a[j] <= n/i;j++){st[a[j]*i]=true;if(i%a[j]==0) break;}}
}

题目：868. 筛质数 - AcWing题库

代码：

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;int n,res,a[1000010];
//开个bool数组来记录当前数是否为质数
bool st[1000010];void get_prime(int n)
{for(int i=2;i<=n;i++){//如果被筛选后仍为false,则为质数,我们就将其记录下来。if(!st[i]) a[res++]=i;//每一个数只会被它的最小质因子筛去//枚举每一个质数for(int j=0;a[j] <= n/i;j++)/*这里a[j]退出循环的条件我们展开来看：a[j]*i<=n如果a[j]再增加，那么a[j]*i的值就会>n，筛n之外的非质数对于题干要求来说没什么意义*/{/*比如这里的i=27，那么在第一次会把st[2*27]筛出去，第二次把st[3*27]筛出去第三次把st[5*27]但是第三次的筛选是没有任何意义的因为5*27=45*3;所以5*27应该由它的最小质数3所筛去*/st[a[j]*i]=true;//如果i%a[j]==0那么a[j]一定是i的最小质因子，如果不break掉，那么一定会造成后续的数重复被标记if(i%a[j]==0) break;//a[j]一定是i的最小质因子，因为a[i]是从小到大进行枚举}}
}int main()
{cin >> n;get_prime(n);cout << res << endl;return 0;
}