GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

A22611. $筛选法找质数$

填空题较难

知识点

筛选法质数数组

题目描述

筛选法找质数 题目描述 用筛法求出n(2\leqn\leq1000)以内的全部质数。 输入 输入n。 输出 多行，由小到大的质数。 输入样例 10 输出样例 2 3 5 7

参考答案

#include <bits/stdc++.h>
using namespace std;
bool isPrime[10005];//isPrime[i]：i是否是质数 
void initPrime(int n)//n：数字范围 
{
	memset(isPrime, 1, sizeof(isPrime));
	for(int i = 2; i*i <= n; ++i) if(isPrime[i])
		for(int j = i*i; j <= n; j += i)
			isPrime[j] = false;
}
int main()
{
   	int n;
   	cin >> n;
   	initPrime(n);
	for(int i = 2; i <= n; ++i) if(isPrime[i])
		cout << i << endl;
	return 0;
}

上一题下一题