质数

质数的判定-试除法

质数的因子一定是成对出现的，因此不必枚举所有的因子，只要枚举其中较小的因子，也就是一半的因子即可。而较小因子的上限是sqrt(n)，所以只需到sqrt即可。

#include <bits/stdc++.h>
using namespace std;

bool is_prime(int u)
{
    if (u < 2) return false;
    for (int i = 2; i <= u / i; i ++ ){
        if (u % i == 0) return true;
    }
    return false;
}

int main()
{
    int n;
    cin >> n;
    while (n -- ){
        int x;
        cin >> x;
        if (is_prime(x)) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}

分解质因数-试除法

质因数是指能整除给定数的质数。同时，两个没有共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。只有一个质因子的正整数为质数。

#include <bits/stdc++.h>
using namespace std;

void devide(int u)
{
    for (int i = 2; i <= u / i; i ++ ){
        if (u % i == 0){
            int s = 0;
            while (u % i == 0){
                u /= i; // 分解过程
                s ++ ;
            }
            printf("%d %d\n", i, s);
        }
    }
    if (u > 1) printf("%d 1\n", u); // 一个数最多只包含一个大于sqrtn的因子，如果u还未被除尽，说明现在的u就等于这个因子
    printf("\n");
}

int main()
{
    int n;
    cin >> n;
    while (n -- ){
        int x;
        cin >> x;
        devide(x);
    }

    return 0;
}

素数筛

普通筛法（埃氏筛）

素数筛与预处理相似，通过把i的倍数删去，剩余的即是素数

#include <iostream>
#include <algorithm>

using namespace std;

const int N= 1000010;

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

int main()
{
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}

但埃氏筛法比较暴力，有许多数被重复筛去，增加了不必要的循环，比较多余。

线性筛法（欧拉筛法）

线性筛法保证每一个合数只被筛去一次，但合数的因子可能有多个素数，对于一个数c=ab(b为c的最小质因数），当通过该算法的循环循环至c * b时，易得此时c%b==0,如果此时继续循环至b后面的一个素数d，则有：cd=a * b * d=(ad)b，因为d>b,所以a * d>c。当循环从c继续查找到a * d时我们发现当ad再次与素数b想乘时，就又对c * d进行了一次操作，出现了冗余，所以在if(n%prime[j]==0)成立时要将该层循环break掉；

1)当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j]<i的最小质因子,所以primes[j]*i的最小质因子就是primes[j];
2)当有i%primes[j]==0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是prime[j]，之后接着用st[primes[j+1]*i]=true去筛合数时，就不是用最小质因子去更新了,因为i有最小质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子，此时就应该退出循环，避免之后重复进行筛选。

举个例子，对于一个数9，9 * 2=18将18标记为合数，循环继续；9 * 3=27将27标记为合数，此时发现9%3=0，循环退出。如果将循环继续下去会出现筛除9*5=45的情况，而45=15 * 3，在15时会被在筛去一次，故不可行

#include <iostream>
#include <algorithm>

using namespace std;

const int N= 1000010;

int primes[N], cnt;
bool st[N];

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

int main()
{
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}