当前位置:   article > 正文

四种质数筛选算法总结(c++)_素数筛c++

素数筛c++


参考自: leetcode题解,计数质数

质数筛选

质数:除了1和它本身以外不再有其他因数的自然数。

合数:与质数相反。

枚举法

枚举法是查找质数最容易想到的方法,又被称为试除法。

它的思路就是遍历从2到n这个数的所有的数字,判断这个数字能否被这个序列种的任意一个序列整除,如果整除,则说明它不具有唯一的因子(1和它本身)

代码如下:

int func(int n)
{
    int ans = 0;
    bool isPrimer;
    for (int i = 2; i < n; i++)
    {
        isPrimer = true;		//默认其是一个质数
        for (int j = 2; j < i; j++)
        {
            if (i % j == 0)
            {	//如果有任意一个数能够被整除,则说明其一定不是质数,则直接退出
                isPrimer = false;
                break;
            }
        }
        if (isPrimer)	//如果是质数,则递增
        {
            ans++;
        }
    }
    return ans;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

枚举优化

观察以下数字的形式:

4: 1 * 4 ,2 * 2 , 4 * 1

5: 1* 5 ,sqrt(5) * sqrt(5) , 5 * 1

6: 1* 6 ,2 * 3 ,sqrt(6) * sqrt(6) ,3 * 2 , 6 * 1

8: 1* 6 ,2 * 4 ,sqrt(8) * sqrt(8) ,4 * 2 , 6 * 1

可以得到,无论数字是质数还是合数,可以认为以中间的两个因子相乘,他们的左右两边是一致的。也就是说,遍历了前面,我们如果继续遍历,则会导致重复的现象出现,则我们完全可以避免他。

优化一个地方:

...
for (int j=2;j<=sqrt(i);j++)	//只遍历前面的sqrt部分即可
...
  • 1
  • 2
  • 3

埃氏筛

引论: 一个质数的倍数一定是合数 ,如 3 是一个质数,则 3 * 3 , 3 * 3 + 3 , 3 * 3 + 3 + 3 一定是合数。

所以我们可以在准备判断一个数字是否是质数的时候,计算他的倍数,把他后面的倍数都计算出来,然后他们一定是合数,我们可以直接排除

我们怎么实现这一点呢,可以定义一个质数数组,一共有n个数字,则用n个数字 1 填充数组。

  1. 依次取出每一个数字,当其在数组里为1时,则它是一个质数。
  2. 计算这个数字的倍数,则这些数字一定是合数,它所对应的数组里全部都置为0。
  3. 质数数组里:为1:质数,为0:合数。

图解:

  1. 绿色区域:数字2影响的区域(即是2的倍数),他们都是合数,直接在数组中标记为 0
  2. 粉色区域: 数字3影响的区域, 同理 。。。。
  3. 一个弊端:不同的数字会产生重合的情况,比如 2 和 3 他们的倍数都会选到 12这个数字,但是12在2的时候就被标记了,就没必要第二次重复标记了,因此这是一个埃氏筛需要优化的地方。。
    在这里插入图片描述
//埃氏筛
int countPrimes_2(int n) {
    //首先全部初始化为1   
    vector<int> isPrimer(n, 1);
    int ans = 0;
    for (int i = 2; i < n; i++)
    {
        if (isPrimer[i] == 1)
        {
            ans++;
            if ((long long) i*i < n)	//注意首先判断第一个 i*i是否位于这个区间种
            {
                //将其 x(x+1) x(x+2) 倍数全部设置为0,即一定是非奇数
                for (int j = i * i; j < n; j += i)
                {
                    isPrimer[j] = 0;
                }
           	}
        }
    }
    return ans;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

线氏筛

在埃氏筛中,我们存储重复标记元素的情况,我们无法避免它,但是我们利用线氏筛来完全避免这种情况

根据《算术基本定理》:

算术基本定理: 任何一个大于1的 自然数 N,如果N不为 质数 ,那么N可以 唯一 分解成有限个质数的乘积.

例如:

  • 16是一个合数,16可以 分解为 2 * 2 * 2 *2 是一个唯一的,有限个的质数乘积。

  • 20 是一个合数,20 可以分解为 2 * 2 * 5 也是一个唯一的,有限个的质数的乘积。

因此得到结论:

  • 有限多个质数的乘积 一定是一个合数 ---->质数 * 质数 * 质数 … = 合数

  • 作为因子的每个质数不同,则最终的合数也不同。

  • 临时存储每一个质数,只要后面的数字能够被这些质数整除,则直接结束循环,原因:

    • 当前数 能被 质数数组中的某质数 整除,当前数一定是包含 该质数 的合数

    • 合数拆分时,因子中,会出现 两个相同质数,不能保证合数不同

    • 质数数组中后面质数都比 该质数 大。该质数 * >它的质数 = 合数后面一定会遇到

图例:

  1. 首先看数字2,它是质数,然后把这个数字放在质数数组[ 0 ]中,在确保范围的情况下,然后把2 依次乘以质数数组中每一项,得到的数字一定是合数(质数 * 质数 = 合数),由此,得到 4是合数,则标记为非质数 0
  2. 再来看数字3,它是质数,放入质数数组 [ 1 ]中,在确保范围的情况下,把3依次乘以质数数组中的每一项,得到6 和 9 因此,这两个数字也一定是合数,标识为 0
  3. 再来看数字4,它是合数,因此不用放入质数数组中,在确保范围的情况下,用4乘以质数数组中的每一项,得到 8 ( 4 * 2),你是否以为还是有数字12? 答案是并没有,因为,数字4能被质数数组中的第一项(2)整除,我的理解: 12可以被拆分为 2 * 2 * 3,2和3都在质数数组中出现了,因此就没有必要再利用3 * 4得到 12了,因为4可以由 2 * 2得到,因此直接结束此次循环
  4. 数字5,确定 10 和 15 不是质数 …

在这里插入图片描述

//线氏筛
    int countPrimes_1(int n) {
        vector<int> primes;
        vector<int> isPrime(n, 1);
        for (int i = 2; i < n; ++i) {
            if (isPrime[i]) {
                primes.push_back(i);
            }
            for (int j = 0; j < primes.size() && i * primes[j] < n; ++j) {
                isPrime[i * primes[j]] = 0;
                if (i % primes[j] == 0) {
                    break;
                }
            }
        }
        return primes.size();
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

奇数筛

优化后的埃氏筛:

  • 偶数一定不是质数! 因此只遍历每一个奇数就可以
  • 奇数 * 偶数 = 偶数,因此不必讨论这种情况。
  • 奇数 * 奇数 =奇数,因此只在奇数范围内寻找
class Solution {
public:
    int countPrimes(int n) {
        //默认全部为true
        vector<int> primer(n,1);
        int res=(n>2)?1:0;
        int t=0;
        for (int i=3;i<n;i+=2)
        {
            if (primer[i]==1)
            {
                res++;
                if ((long long)i*i < n)
                {
                    for (int j=i;(t=i*j)<n;j+=2)
                    {
                        primer[t]=0;
                    }
                }
            }
        }
        return res;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号