1913: 快速查找素数

骑猪看日落 2024-02-18 22:11 40阅读 0赞

###    **1913: 快速查找素数** ###

时间限制: 4 Sec 内存限制: 64 MB  
提交: 132 解决: 48  
您该题的状态：**已完成**  
\[[提交][Link 1]\]\[[状态][Link 2]\]\[[讨论版][Link 3]\]

### **题目描述** ###

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

### **输入** ###

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

### **输出** ###

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

### **样例输入** ###

<span style="color:#333333"><span style="color:black">5
    10
    11
    0</span></span>

### **样例输出** ###

<span style="color:#333333"><span style="color:black">2 3 5
    2 3 5 7
    2 3 5 7 11
    </span></span>

### **提示** ###

### **来源** ###

这题用常规方法，绝对时间超限，用筛选法求素数，开了个2000000的数组，居然没有爆内存，哈哈，

还有用memset置不了一，这点很好奇。找到原因了，该函数对数组操作时只能用于数组的置0或-1，其他值无效。

\#include<iostream>  
\#include<string.h>  
\#include<math.h>  
using namespace std;  
\#define N 2000000//N的大小可以根据需要变化  
int a\[N\];//利用数组的下标记录要判断的数字  
int main()  
\{  
memset(a,0,sizeof(a));//对数组a进行初始化为0，不是素数的标记为1，剩下为0的就是素数了  
a\[1\]=1;//1既不是素数也不是合数，先标记为0  
for(int i=2; i<=sqrt(N); i++)  
\{  
if(a\[i\]==0)//如果i是素数  
\{  
for(int j=2; j\*i<=N; j++) //循环标记的范围是i\*j<N  
\{  
a\[i\*j\]=1;//如果i是素数，那么i\*j肯定不是素数  
\}  
\}  
\}  
int n,m,j,i;  
while(~scanf("%d",&n),n)  
\{  
for(i=2,j=0;i<=n;i++)  
if(a\[i\]==0)  
\{  
if(j==0)  
cout<<i;  
else  
cout<<" "<<i;  
j++;  
\}  
cout<<endl;  
\}  
return 0;  
\}

[Link 1]: http://xyoj.xynu.edu.cn/submitpage.php?id=1913
[Link 2]: http://xyoj.xynu.edu.cn/problemstatus.php?id=1913
[Link 3]: http://xyoj.xynu.edu.cn/bbs.php?pid=1913

发表评论取消回复

表情：

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

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

相关阅读

相关 1913: 快速查找素数

1913: 快速查找素数时间限制: 4 Sec 内存限制: 64 MB 提交: 132 解决: 48 您该题的状态：已完成 \[[提交][Link 1

骑猪看日落/ 2024年02月18日 22:11/ 0 赞/ 41 阅读

相关 java查找回文素数

素数：除了1和本身不能被整除的数。如1,3,11 回文数：从左边读和从右边读一样的数。如：11，22，151，313, 解题思想：先判断是否是素数，再判断是否是回文数。难点

小咪咪/ 2023年10月09日 12:32/ 0 赞/ 19 阅读

相关素数的查找和判断

> 首先我们得先知道素数是什么？素数也就是质数，大于2的一个只能被自己整除的数，如2 、3、5 、7等；所以利用这个特点可以进行编程，从而查找素数，例如查找100--200之间

浅浅的花香味﹌/ 2023年09月23日 13:27/ 0 赞/ 40 阅读

相关六倍素数法（快速）

六倍素数法：对于大于等于5的数我们可以用6的倍数表示， 6n-1 6n 6n+1 6n+2 6n+3 6n+4 5 -----6 – 7 ---- -8 ----

阳光穿透心脏的1/2处/ 2023年07月20日 13:37/ 0 赞/ 14 阅读

相关南阳题目187-快速查找素数

快速查找素数时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述现在给你一个正整数N，要你快速的找出在2.....N这些数里面所有的素

左手的ㄟ右手/ 2022年08月20日 08:23/ 0 赞/ 163 阅读

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

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

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

相关关于快速寻找素数的方法

利用素数筛选法进行素数的快速查找。原理很简单，素数一定是奇数，素数的倍数一定不是素数。思路如下：预定义N表示10000，即表示查找10000以内的素数，首先定义数组

左手的ㄟ右手/ 2022年07月12日 10:29/ 0 赞/ 199 阅读

相关快速打印素数表和判断素数模板

判断一个数是否为素数： int isPrime(int k) { int j; for ( j=2; j<=sqrt(k)

柔光的暖阳◎/ 2022年05月31日 02:12/ 0 赞/ 211 阅读

相关素数的快速判断方法

原理大于等于5的素数与6的倍数相邻证明所有自然数可以用集合`A = { 6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5 }`表示，其中 `

电玩女神/ 2022年01月28日 10:41/ 0 赞/ 302 阅读

相关素数快速打表的方法

素数这个东西在编程的时候经常用到，下面给出一种快速打出一定量素数的代码。 ![ContractedBlock.gif][] ![ExpandedBlockStart

ゞ浴缸里的玫瑰/ 2021年11月11日 11:48/ 0 赞/ 328 阅读