素数筛模板

约定不等于承诺〃 2022-11-06 00:59 174阅读 0赞

## 查找N内所有素数 ##

### 1.埃氏筛 ###

#include<iostream>
    
    using namespace std;
    
    typedef long long ll;
    
    const int N = 2e7+10;
    
    int prime[N];
    bool vis[N];
    long long idx = 0;
    
    void aishi(){
        
        for(ll i = 2; i < N; i++){
        
            if(!vis[i]) {
        
                prime[idx++] = i;
                for(ll j = i*i; j < N; j+=i){
        
                    vis[j] = true;
                }
            }
        }
    }
    
    int main()
    {
        
        aishi();
        cout << idx << endl;
        for(int i = 0; i < idx; i++){
        
            cout << prime[i] << ' ';
        }
    }

### 2.欧拉筛 ###

#include<iostream>
    
    using namespace std;
    
    typedef long long ll;
    
    const int N = 2e7+10;
    
    int prime[N];
    bool vis[N];
    long long idx = 0;
    
    void oula(){
        
        for(ll i = 2; i < N; i++){
        
            if(!vis[i]) prime[idx++] = i;
            for(int j = 0; j < idx && i*prime[j] < N; j++){
        
                vis[i*prime[j]] = true;
                if(i%prime[j] == 0) break;
            }
        }
    }
    
    int main()
    {
        
        oula();
        cout << idx << endl;
        for(int i = 0; i < idx; i++){
        
            cout << prime[i] << ' ';
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，174人围观）

还没有评论，来说两句吧...

相关阅读

相关素数筛

目录题目思路1 思路2 思路3 题目给定一个正整数n(2≤n≤10000)，先输出2~n之间的素数个数

拼搏现实的明天。/ 2023年10月06日 16:35/ 0 赞/ 66 阅读

相关 P3383 【模板】线性筛素数---洛谷

题目描述题目背景本题已更新，从判断素数改为了查询第 k 小的素数提示：如果你使用 cin 来读入，建议使用 std::ios::sync\_with\_st

雨点打透心脏的1/2处/ 2023年07月18日 06:54/ 0 赞/ 19 阅读

相关 ACM.素数筛

一.埃氏筛筛法的思想是去除要求范围内所有的合数，剩下的就是素数了，而任何合数都可以表示为素数的乘积，因此如果已知一个数为素数，则它的倍数都为合数。合数的倍数一定会在

清疚/ 2023年07月05日 11:57/ 0 赞/ 28 阅读

相关 POJ 2689【筛法求素数+区间筛素数】

Discription The branch of mathematics called number theory is about properties of numb

桃扇骨/ 2023年07月04日 06:15/ 0 赞/ 37 阅读

相关欧拉线性筛法（素数模板）

什么是素数？ ans：素数也又称质数。一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数叫做质数。最小的质数是 2，它也是唯一的偶数质数。最前面的质

╰半橙微兮°/ 2023年07月01日 15:00/ 0 赞/ 1 阅读

相关素数筛模板

查找N内所有素数 1.埃氏筛 include<iostream> using namespace std; typede

约定不等于承诺〃/ 2022年11月06日 00:59/ 0 赞/ 175 阅读

相关素数线性筛模板

[参考于该博客][Link 1] int Mark[MAXSIZE]; int prime[MAXSIZE]; //判断是

╰+哭是因爲堅強的太久メ/ 2022年05月14日 03:36/ 0 赞/ 252 阅读

相关筛法求素数

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时

我不是女神ヾ/ 2022年05月12日 14:42/ 0 赞/ 276 阅读

相关素数筛法

//暴力枚举素数筛法 o(n 根号n) for(int i=2;i<=n;i++){ bool g=0; for(int j=2;jj<

╰+哭是因爲堅強的太久メ/ 2022年04月04日 10:54/ 0 赞/ 277 阅读

相关素数筛C++

埃拉托斯特尼筛法（sieve of Eratosthenes ）是古希腊数学家埃拉托斯特尼发明的计算素数的方法。对于求解不大于n的所有素数，我们先找出sqrt(n)内的所有素

向右看齐/ 2022年02月09日 11:15/ 0 赞/ 299 阅读