文章
20
粉丝
224
获赞
57
访问
138.7k
#include<stdio.h>
#include<string.h>
// 线性素数筛选 prime[0]存的是素数的个数
#define maxn 1000000 + 5 // 这里要用宏定义,如果用const的话会编译错误:variably modified ‘prime’ at file scope
int prime[maxn];
void getPrime() {
memset(prime, 0, sizeof(prime));
for (int i = 2; i <= maxn; ++i) {
if (!prime[i]) prime[++prime[0]] = i;
for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; ++j) {
prime[prime[j] * i] = 1;
if (i % prime[j] == 0) break;
}
}
}
int main() {
getPrime(); // 先进行素数筛选预处理
int n;
while (scanf("%d", &n) != EOF) {
int num = 0, ans[n]; // 存储答案的个数和数组
for (int i = 1; i <= prime[0]; ++i) {
if (prime[i] <= n && prime[i] % 10 == 1) ans[num++] = prime[i];
}
for (int i = 0; i < num; ++i) {
if (i != num-1) printf("%d ", ans[i]);
else printf("%d\n", ans[i]); // 最后一个素数后面没有空格,而是换行
}
if (num == 0) printf("-1\n");
}
}
登录后发布评论
暂无评论,来抢沙发