[数论](1)质数

质数

一、判质数

思路:从定义除法再做优化即可

质数的概念:质数是指在大于 1 的自然数中,除了 1 和它本身不再有其他因数的自然数

伪码:

```C++ 给定一个x,判断其是否是质数: 如果x小于2,则直接返回false(质数是从2开始定义的) i 从2开始迭代,直到 x/i 若存在[ x % i == 0 ] 则代表其有除1和它本身外还有其他因数 则返回false

(优化:因为因子是成对出现的,所有只需要枚举比它小的那个数即可)
返回true

源码:

```C++
int get_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)//因为质数是成对出现的
        if (x % i == 0) return false;
    return true;
}

二、分解质因数

思路:短除法是从最小的质数除起,一直除到结果为质数为止

伪码:

```C++ 给定一个x,分解其质因数 i 从 2 开始迭代,直到 x / i 若存在 [x % i == 0] 则代表 i 为 x 的质因子 将这个质因子除干净 直到 [x % i != 0] 输出这个 质因子 和 其指数 若存在 [x > 1] 则代表其有一个大于 x/i 的质因子,输出即可。

(从2开始不会迭代到合数是因为是从其最小质因子开始枚举的,合数会在除尽质因子的同时除掉,比如4会在除尽2的时候被除掉)

源码:

```C++
for (int i = 2; i <= x / i; i++) {
        if(x%i==0){//若[ i 能整除 x ]成立立
            int s = 0;//质因子的次数
            while (x % i==0) {//将当前i除干净
                x /= i;
                  s++;
            }
            printf("%d %d\n",  i, s);//i为质因子,s为该质因子出现的次数
        }
}
if (x > 1) printf("%d %d\n", x, 1);
printf("\n");

三、筛质数

埃氏筛法:

思路:要得到自然数n以内的全部素数,必须把不大于[ x / i ]的所有素数的倍数剔除,剩下的就是素数。

给出要筛数值的范围n,找出以内的素数。先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去......

伪码:

```C++ 给定一个x,筛出x以内的所有质数 定义一个prime数组,用于存储质数,cnt用于计数,st用于标记 i 从 2 开始迭代,直到 [i <= x] 若 i 当前未被标记,即存在 [st[i] == false],代表当前质数未被标记 则将当前质数标记,然后 prime[cnt++]=i 再将其倍数全部标记即可(倍数只需枚举到x)

(由于质数是从小开始枚举,即合数会在枚举当前质数的时候被筛掉)

源码:

```C++
bool st[N];//标记数组
int prime[N];//记录质数的数组
int cnt;//prime数组的下标
void get_prime(int x) {
    for (int i = 2; i <= x; i++) {//从2开始枚举,筛出[ 1 - n ]中所有的质数
        if (!st[i]) {//若当前质因子未被标记,则代表其为质数
            st[i] = true;
            prime[cnt++] = i;//记录质数
            for (int j = i + i; j <= n; j += i)//将n中所有i的倍数全部标记
                st[j] = true;
        }
    }
    return;
}

线性筛法:

思路:在埃氏筛法的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。在埃氏筛法中,6会被2的3倍筛掉,也会被3的2倍筛掉

伪码:

```C++ 给定一个x,筛出x以内的所有质数 定义一个prime数组,用于存储质数,cnt用于计数,st用于标记 i 从 2 开始迭代,直到 [i <= x] 若 i 当前未被标记,即存在 [st[i] == false] 则将其加入prime数组内 j从0开始迭代,直到 prime[j]i 大于 x/i 将st[prime[j]i]全部标记(实现了每个数都只被其最小质因子筛掉) 当i%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的最小质因子,此时就应该 退出循环,避免之后重复进行筛选。


源码:

```C++
int prime[N];//记录质数的数组
bool st[N];//标记数组
int cnt;//prime数组的下标
void get_prime(int x){
    for(int i=2;i<=x;i++){//i从2开始枚举,筛出所有 1-x 中的质数
        if(!st[i]) prime[cnt++]=i;//如果当前i未被标记,则代表其是质数,将其记录下来
        for(int j=0;prime[j]*i<=x;j++){//从最小质因子开始,枚举 x 范围内所有这个 [ 质因子的倍数 ]
            st[prime[j]*i]=true;//将其倍数标记
            if(i%prime[j]==0) break;//若当前最小质因子是 i 的最小质因子,则退出(这个优化让整体时间变为线性) 
        }
    }
    return;
}

本文链接:

https://nullcode.fun/139.html
1 + 9 =
快来做第一个评论的人吧~