AOJ_0009（Prime Number）

テーマリンクhttp://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34870
この問題は与えられた整数nを求めて、それより小さい素数の個数を求めます。表を打つ方法で処理します。acコードは以下の通りです。

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>

using namespace std;
typedef long long int ll;
const int maxn = 10000000 + 10;
ll prime[maxn / 10];
bool is_prime[maxn];

void get_prime()
{
	int i, j;
	memset(prime, 0, sizeof(prime));
	for (i = 0; i<maxn; i++)
		is_prime[i] = true;
	is_prime[0] = is_prime[1] = false;
	for (i = 2; i<maxn; i++)
	{
		if (is_prime[i])               //     
		{
			prime[++prime[0]] = i;    //prime[0]         
		}
		for (j = i * 2; j<maxn; j += i)      //    i，    
		{
			is_prime[j] = false;
		}
	}
}
int main(void)
{
	//freopen("in.txt", "r", stdin);
	get_prime();
	ll n;

	while (scanf("%lld", &n) != EOF)
	{
		int i;
		for (i = 1; i<maxn / 10; i++)
		{
			if (prime[i]>n)                   //i   0  ，  prime[0]         
				break;                        //         n   ，i     
		}
		printf("%d
", i - 1);
	}
	return 0;
}