埃拉托斯特尼筛法快速查找素数

待我称王封你为后i 2022-08-09 12:54 196阅读 0赞

[埃拉托斯特尼筛法][Link 1]

## 快速查找素数 ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 3

描述

现在给你一个正整数N，要你快速的找出在2.....N这些数里面所有的素数。

输入

给出一个正整数数N(N<=2000000)  
但N为0时结束程序。  
测试数据不超过100组

输出

将2~N范围内所有的素数输出。两个数之间用空格隔开

样例输入

5
    10
    11
    0

样例输出

2 3 5
    2 3 5 7
    2 3 5 7 11

来源

[经典题][Link 2]

上传者

[路过这][Link 3]

思路参见wiki的解释。复杂度是接近线性的。

![复制代码][copycode.gif]

#include<stdio.h>
    #include<string.h>
    #define MAX 2000001
    int all[MAX];
    int N,i,j,s;
    int main()
    {
        memset(all,1,sizeof(all));
        for(i=2;i<=MAX;i++)
            if(all[i])
                for(j=i+i;j<=MAX;j+=i)
                    all[j]=0;
        while(scanf("%d",&N),N)
        {
            for(i=2;i<=N;i++)
                if(all[i])
                    printf("%d ",i);
            printf("\n");
        }
        return 0;
    }

![复制代码][copycode.gif]

[Link 1]: http://www.cnblogs.com/yuris115/p/3416980.html
[Link 2]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%E7%BB%8F%E5%85%B8%E9%A2%98
[Link 3]: http://acm.nyist.net/JudgeOnline/profile.php?userid=%E8%B7%AF%E8%BF%87%E8%BF%99
[copycode.gif]: /images/20220731/afdedb179b8f4aa1a5b2fccd7e1e4c5b.png

发表评论取消回复

表情：

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

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

相关阅读

相关素数筛选法（埃拉托斯特尼筛法）

统计所有小于非负整数 n 的质数的数量。示例 1：输入：n = 10 输出：4 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。示

阳光穿透心脏的1/2处/ 2022年12月25日 05:56/ 0 赞/ 180 阅读

相关埃拉托斯特尼筛法快速查找素数

[埃拉托斯特尼筛法][Link 1] 快速查找素数时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述现在给你一个正整数N

待我称王封你为后i/ 2022年08月09日 12:54/ 0 赞/ 197 阅读

相关求解素数-埃拉托斯特尼筛法

该算法来自百度百科 def primes(n): P = [] f = [] for i in range(n+1)

今天药忘吃喽~/ 2022年08月09日 12:46/ 0 赞/ 209 阅读

相关【基础练习】埃拉托色尼筛法求质数

跑了一个质数表，哈希可能能用到一开始跑的是0x3f3f3f3f以内，这个数等于1061109567 十亿多一点结果什么软件也打不开那么大的文件里奥说估计有一亿多个质数

分手后的思念是犯贱/ 2022年08月04日 08:28/ 0 赞/ 205 阅读

相关 python实现埃拉托色尼筛选法（素数筛选法）

def sieve_of_eratosthenes(n):埃拉托色尼筛选法，返回少于n的素数 primes = [True] (n+1)范围0到n的列

青旅半醒/ 2022年05月30日 05:19/ 0 赞/ 502 阅读

相关埃拉托斯特尼筛法（素数高效筛选）

一、素数定义素数又称质数（prime number），指所有大于1的数中只能被1和它本身整除的数。二、埃拉托斯特尼筛法（Sieve of Eratosthenes

╰半夏微凉°/ 2022年05月25日 01:56/ 0 赞/ 254 阅读

相关判断一个数是否是质数---埃拉托斯特尼筛法

1、题目： Count the number of prime numbers less than a non-negative number, n. Example:

谁践踏了优雅/ 2022年05月22日 04:40/ 0 赞/ 181 阅读

相关 Sweet Snippet 系列之埃拉托斯特尼(Eratosthenes)筛法

> 埃拉托斯特尼(Eratosthenes)筛法的简单实现遴选素数的埃拉托斯特尼(Eratosthenes)筛法想必大家都不陌生,不熟悉的朋友可以看看wiki,在此简单列出

青旅半醒/ 2021年12月15日 11:43/ 0 赞/ 506 阅读

相关求解n以内的素数之埃拉特斯特尼筛和欧拉筛

首先我像声明一点：我的博客只有干货！！！！！ 1. 埃筛埃筛就是在判断出来一个数是素数之后那么他的倍数全部都是合数缺点就是我们可能对同一个数

一时失言乱红尘/ 2021年12月09日 17:34/ 0 赞/ 319 阅读

相关埃拉托色尼筛法（素数筛）

列举大于等于2的整数，将其倍数划掉，往后遍历发现被划掉的直接略过，还没被划掉的则是质数（表示其不是前面任何一个数的倍数，也即没有除1和本身外的因子）。时间复杂度 O(Nlogl

骑猪看日落/ 2021年07月16日 21:52/ 0 赞/ 416 阅读