质数筛法C++

212 阅读 0 评论 140 点赞

我是靠谱客的博主雪白大门，这篇文章主要介绍质数筛法C++，现在分享给大家，希望可以做个参考。

直接上代码：

#include <iostream>
#include <vector>
using namespace std;
const int n=...; // 范围
vector<bool> vis(n+1, true);//vis用来标记质数,用bool可以节约空间
int prim[n];//prim存当前找到的质数
int cnt = 0;//cnt记录当前为止找到的质数的个数

void init() {//筛法，筛出质数存到prim数组中
    for (int i = 2; i < n; i++) {
        if (vis[i]) prim[cnt++] = i;//i没被标记为合数即为质数，存到prim数组中
        for (int j = 0;; j++) { // 迭代当前质数表
            if (prim[j] * i > n) break;//超出范围
            vis[prim[j] * i] = false;//记录这个质数的倍数是合数
            if (i % prim[j] == 0) break;//保证每个数只被它的最小质因子筛一次
        }
    }
}