[数论](1)质数

质数

一、判质数

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

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

伪码:

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

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

源码:

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

二、分解质因数

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

伪码:

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

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

源码:

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的倍数剔除掉;不断重复下去......

伪码:

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

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

源码:

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倍筛掉

伪码:

给定一个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的最小质因子,此时就应该
退出循环,避免之后重复进行筛选。

源码:

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 + 4 =
快来做第一个评论的人吧~