跳到主要内容

质数筛法

试除法判断质数​

质数：在大于1的整数中，如果只包含1和本身两个约数，就被称为质数，或者叫素数。

判断一个数n是不是质数，只需从2开始一直遍历到根号n即可，因为如果n能被一个小于根号n的数整除，那么必定存在一个大于根号n的数。

代码​

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

注意：写成 i < x / i,不推荐写成 i < sqrt(x)比较慢，i * i < x, 可能会溢出

试除法判断质因数​

质因数（素因数或质因子）：在数论里是指能整除给定正整数的质数。例如：3和5都是15的质因数

合数：是指在大于1的整数中，除了能被1和它本身整除外，还能被其它数整除的数。与合数相对的是质数，而1既不属于质数也不属于合数。

思路：

  • n中最多只包含一个大于sqrt(n)的质因子，如果有2个大于sqrt(n)的质因子，乘在一起，那就大于n了。
  • i枚举到 n / i就可以了也就是，枚举到sqrt(n)
  • 从小到大枚举，此时n中不包含2 ~ i-1之间的质因子,那么如果i是一个合数，并且n % i == 0, 那么n一定会包含i的质因子(2~i-1) 与上面矛盾所以i一定是质数。也可以理解为,大的合数，并且可以整除n的数字，一定会被小的可以整除n的质数筛掉

代码​

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;// 求一下i的次数
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    // 由于枚举到sqrt(n)，那么这时候x > 1，剩下的那个就是比较大的质因子
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

筛质数​

给你一个正整数n，求1-n中质数的个数

朴素法晒质数​

朴素筛法O(nlogn)

算法核心：把每个数的所有倍数筛掉

调和级数：1 + 1/2 + 1/3 +…+ 1/n = lnn + c(c欧拉常数=0.577)

算法时间复杂度：最外层遍历整个数组是n（其实不用管，只用看内部总次数即可），内部循环总次数是n/2,n/3,n/4…1，累加得n(1/2 + 1/3 + 1/4 +…+1/n)=nlnn=nlogn

代码​

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
void get_prime(int x)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++] = i;
		for(int j = i + i ; j <=  n ; j += i) st[j] = true;
    }
}

埃式筛法​

算法核心：把每个质数的所有倍数筛掉

质数定理：1~n中由n/logn个质数

算法时间复杂度：由（1）可得：O（nlonglongn）当数据不是足够大时与O(n)接近

埃氏筛法 O(nloglogn)约为O(n)，仅使用质数筛后面的合数。这样可以保证筛掉所有的合数。

代码​

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue; //st如果是true 说明被筛过，那么它的倍数肯定被筛过，所以直接跳过
        //接下来对该质数的所有倍数进行筛选
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

线性筛法​

算法核心：x只会被它的最小质因数筛去，即每个数字只被筛选一次，因此是线性的n。

  • 证明每个x都能被筛掉：对于一个合数x，x一定存在一个最小质因子，假设pj是x 的最小质因子，当i枚举到x/pj时，x就被筛了，因为x只有一个最小质因数，因此每个数字只被筛选一次。

算法时间复杂杂度：因为每个数只被筛过一次，因此为O(n)

代码​

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

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;//筛去primes[j]的倍数
            if (i % primes[j] == 0) break;//当primes[j]是i的最小质因数时break 			   
            //(为了遵守算法的核心，避免重复的筛选）。如果继续用primes[j+1]去筛选，此时，
            //primes[j+1]大于i的最小质因子，那么也同样不是primes[j+1]*i的最小质因子
        }
    }
}
  • 当i % primes[j] != 0时，说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j] < i的最小质因子，所以primes[j] * i的最小质因子就是primes[j]
  • 当有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的最小质因子，此时就应该退出循环，避免之后重复进行筛选
0%