判断质数 Prime

练习链接: 866. 试除法判定质数

// 很简单， 常用就是试除法，这里主要强调一下细节
#include<iostream>
using namespace std;

auto is_prime(int x) -> bool     
{
    if(x < 2) return false;           // 小于2的数既不是合数也不是质数

     // 这里只要判断前半部分就好了，直接写成开根号太难看，写成 i * i <= x, 如果i很大则会溢出，
     // 故写成这样最好,注意等于条件，判断的是刚好平方等于这个数
    for(int i = 2; i <= x / i; ++i)  
        if(x % i == 0) return false;
    return true;
}

auto main() -> int
{
    int n; cin >> n;
    while(n--)
    {
        int a; cin >> a;
        if(is_prime(a)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

分解质因数

质因数概念， 首先它是一个因数，然后这个因数是质数，例如18的质因数只有 2 , 3, 简单的概念了

练习链接: 867. 分解质因数

#include<iostream>
using namespace std;

auto main() -> int
{
    int n;
    cin >> n;
    while(n--)
    {
        int a; cin >> a;
        if(a < 2)
        {
            cout << endl;
            continue;
        }

        // 思路:既然是找质因数，故从最小的质数2开始看能不能整除，同样试除法
        // 那为啥是从2,++i, 这样不会循环到合数吗，如何保证循环到的是质数呢
        // 因为如果找到一个能整除的数之后我们会进入while把这个数有包含i的部分
        // 给除干净了，所以当循环到i的时候就说明此时的a, 绝对不包含 2 ~ i 的因数
        // 而如果 i 能够整除的话,肯定说明 i 的因数没有2 ~ i 的因数不然不可能整除
        // i 的因数没有2 ~ i 的因数，所以也就说明了i只有1和本身i这两个因数,这不就是质数的定义吗
        // 这里同样做了次处理一半的处理，因为如果前一半都没有因数，那么后面就不可能有
        for(int i = 2; i <= a / i; ++i)    
        {
            int c = 0;
            if(a % i == 0)
            {
                while(a % i == 0) a /= i, c++;
                cout << i << " " << c << endl;
            }
        }
        if(a > 1) cout << a << " " << 1 << endl;
        cout << endl;
    }
    return 0;
}

筛质数 (在一个范围内快速筛选出质数)

相比于判断质数，我们不能在一个范围内一个一个采用试除法判断，因为时间复杂度会很高

这里主要有两种筛法: 1. 埃氏筛法 (朴素筛法), 2. 欧拉筛法 (线性筛)

1. 埃氏筛法

从最小的质数2开始, 我们知道合数一定是质数的倍数，故我们将筛选到的第一个质数时，我们将它的倍数依次标记为合数，当然不用全部标，只用标记到给出的范围即可. 由于是从最小质数开始，故找到的下一个未被标记的数一定也是质数，因为未被标记说明不含2 ~ i - 1 的任何因数，跟上面原理一样。 故将找到的这个新的质数的倍数标记为合数。代码实现

#include<iostream>
using namespace std;

constexpr int N = 1e+6 + 10;
bool st[N];

auto f(int n) -> int
{
    if(n < 2) return 0;
    int cnt = 0;
    for(int i = 2; i <= n; ++i)
    {   
        if(st[i]) continue;
        st[i] = true; cnt++;
        // 这里的话如果在数据不大的情况下可以做个优化, int j = i * i 从这里开始
        // 因为前面的2 ~ i - 1 中，如果是倍数的情况已经标记过了，故从i * i 开始
        // 但这里这样优化的话，i * i 可能会溢出，故这样写保证了不溢出
        for(int j = i + i ; j <= n; j += i)     // 将其倍数标记为合数
            st[j] = true;
    }
    return cnt;
}

auto main() -> int
{
    int n; cin >> n;
    cout << f(n) << endl;
}

1. 欧拉筛

通过观察上面的埃氏筛，我们可以发现其实存在重复标记的情况，例如6这个数字，在2的时候会被标记一次，在3的时候也会被标记一次，故欧拉筛，也叫线性筛，保证了每个合数只被最小的质因数筛掉，即每一个合数只会被标记一次. 其实现原理直接来看代码讲解其相较于上面的算法如何改进

#include<iostream>
using namespace std;
constexpr int N = 1e+6 + 10;
int p[N];
bool st[N];

auto f(int n) -> int
{
    if(n < 2)  return 0;
    int cnt = 0;
    for(int i = 2; i <= n; ++i)
    {
        if(!st[i]) p[++cnt] = i;    // 相比于上面的算法，这里额外多了一个p数组用来保存当前的质数
        for(int j = 1; p[j] <= n / i; ++j)     
        {
            st[i * p[j]] = true; // 每次for将p数组中质数的倍数标记为合数, 这一步貌似跟埃氏筛没啥区别
            if(i % p[j] == 0) break;  // 这一步是这个算法的核心，理解为啥欧拉筛每个数只被标记一次

// 我们首先来看, 如果没有这个if特判break退出会咋样，当 i 能被p[j]整除时,设 m = i / p[j];
// 故我们得到了 i = m * p[j], 然后我们的for继续，则标记下一个合数为 i * p[j + 1] , 将我们的i代入得
//  m * p[j] * p[j + 1] --->  (m * p[j + 1]) * p[j], 故这里我们就发现了当我们的i循环到 i = (m * p[j + 1]) 时又会被标记一次,
// 同理 i * p[j + 2] .....也是这种情况， 故这里break退出, 因为后面会会标记. 这样就保证了每个数只会被最小的质因数筛选掉

        }
    }
    return cnt;
}

auto main() -> int
{
    int n; cin >> n;
    cout << f(n) << endl;
    return 0;
}