0009 - Prime Number / AizuOnlineJudge

問題 : 素数 | Aizu Online Judge

#include <iostream>
using namespace std;

#define MAX 1000000

bool is_prime[MAX+1];

void Sieve(void)	{
	for (int i=0; i<=MAX; ++i)
		is_prime[i]=true;
	is_prime[0]=is_prime[1]=false;
	for (int i=2; i<=MAX; ++i)
		if (is_prime[i])
			for (int j=i*2; j<=MAX; j+=i)
				is_prime[j]=false;
}

void Solve(int n)	{
	int answer=0;

	for (int i=2; i<=n; ++i)
		if (is_prime[i])	++answer;
	cout << answer << endl;
}

int main(void)	{
	int n;

	Sieve();
	while (cin >> n)
		Solve(n);
	return 0;
}

蟻本に掲載されているエラトステネスの篩を用いて素数を列挙。
入力した数値以下の素数の数を出力。
～了～