输出指定范围内的素数（质数）
发布时间
阅读量：
阅读量
这里最近看到了这个Sieve of Eratosthenes的方法, 突然意识到过去一直手动枚举每个数字, 这种做法效率低下
先说一下我理解的原理：
首先任何比2大的合数都可以表示为一个素数与一个正整数的乘积基于此就可以开始推导下面的方法
问题：求1-n的所有素数
步骤：
初始化一个大小为n的数组A，并将其第一个元素设置为非素数值；接着将其第二个元素设置为首元素值（即设定其位次位置）；随后在3至n范围内的所有偶数值被确定为合数值；最后令变量K被赋值2。
2、判断A中大于K的数是否已经全部被标记或者K等于n，如果是空跳到第4步；
3、找出A中最小的未被标注过的数字m，并将其标注为素数值；接着，在B中标记所有m的倍数值为合数值；最后将当前找到的素数值赋予K，并返回到步骤2
4、输出数组A中所有素数。
下面贴出代码：
#include <stdio.h>
#include <Windows.h>
#define UNLABELED 0 //未标记
#define PRINE 1 //素数
#define COMPOSITE 2 //合数
#define NOPRINE 3 //非素数
#define SIZE 100
int main()
{
int i = 0; //i表示整数和对应的下标
int j = 0; //j表示正要处理的素数j之前的已处理j之后的未处理
int k = 0; //k表示正在处理的j的倍数从2开始到 j * k < SIZE
int *p = NULL; //控制循环
int a[SIZE + 1] = { 0 }; //下标表示整数内容判断是否为素数
for (p = a; p < a + SIZE; ++p) { //初始化数组全是UNLABELED
*p = UNLABELED;
}
p = NULL;
a[0] = a[1] = NOPRINE; //设置前面两个不是素数的数的状态为NOPRINE
i = 2;
while (i < SIZE + 1) {
//判断是否未标记,找到下一个素数
if (a[i] == UNLABELED) {
j = i;
a[i++] = PRINE;
}
else {
//已经标记了继续i++向下走
i++;
continue;
}
for (k = 2; j * k < SIZE; ++k) { //处理素数的倍数
a[j * k] = COMPOSITE;
}
}
for (p = a; p < a + SIZE; ++p) { //打印出素数
if (*p == PRINE) {
printf("%8d", p - a);
}
}
p = NULL;
printf("\n");
system("pause");
return 0;
}
代码解读我想看看运行结果。之前没有认真检查过。计算到一千时发现未被访问到了错误信息的出现。100的时候则出现了错误信息也出现了。
一个是1-100
这个是1-1000
-_-.
全部评论 (0)
还没有任何评论哟~