素数筛模板

约定不等于承诺〃 2022-11-06 00:59 159阅读 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 条评论，159人围观）

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

相关阅读

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

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

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

相关 ACM.素数筛

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

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

相关素数筛模板

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

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

相关素数筛法略

用筛法求素数的基本原理，是把从1开始的某一范围内的正整数从小到大顺序排列，逐步筛掉非素数留下素数。用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列

墨蓝/ 2022年10月25日 01:23/ 0 赞/ 180 阅读

相关素数线性筛模板

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

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

相关筛法求素数

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

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

相关素数筛法

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

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

相关素数筛C++

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

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

相关数论2：素数筛

埃氏筛判断素数可通过试除小于\\(\\sqrt n\\)的素数来实现，那么将其反过来，只要将\\(<= \\sqrt n\\)的素数的倍数都删掉，那么就能得到一张\\(

向右看齐/ 2021年09月20日 11:56/ 0 赞/ 372 阅读

相关筛法判断素数

1.埃氏筛选法 include <iostream> include <algorithm> using namespace std; con

ゝ一纸荒年。/ 2021年06月22日 15:37/ 0 赞/ 445 阅读