文章

20

粉丝

224

获赞

56

访问

136.8k

头像
线性素数筛选
P1375 北京航空航天大学机试题
发布于2022年2月2日 11:52
阅读数 4.6k

#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");
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发