..质数..

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

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;
}