质数中的质数
题目
思路
1.纯bool类型数组
2.第一次错误是卡在了循环停止条件，maxlen * maxlen » maxlen,数组开小了
3.第二次错误也是卡在了循环停止条件，sqrt（maxlen）最大情况是maxlen，小了就未覆盖一半的区域
代码部分
#include <cstdio>
#include <cstring>
#include <cmath>
#include <windows.h>
#include <iostream>
#define maxlen 1000001
using namespace std;
int main() {
int looplen = sqrt(maxlen);
bool n[maxlen + 100];
bool m[maxlen + 100];
memset(n, true, sizeof(n));
memset(m, true, sizeof(m));
n[0] = false; n[1] = false;
for (int i = 2; i <= looplen; i++) { //一筛
for (int j = i; i*j<=maxlen+10; j++) {
n[i * j] = false;
}
}
for (int i = 0; i <= (maxlen + 100); i++) //复制
m[i] = n[i];
int cnt = 0;
for (int i = 2; i <= maxlen; i++) { //二筛
if (n[i]) {
cnt++;
if (!n[cnt])
m[i] = false;
}
}
int num;
scanf("%d", &num);
for (int i = num; i <= maxlen; i++) {
if (m[i]) {
printf("%d\n", i);
break;
}
}
}
运行截图
