AOJ 0009 Prime Number 题解 《挑战程序设计竞赛》

AOJ 0009 Prime Number

n以内的素数个数：……

2.6 数学问题的解题窍门

素数

艾氏筛法就行了。

我将码农场的UEditor里的代码高亮插件替换升级了下，这样在小屏PC和移动端上代码框会显示横向滚动条，再也不怕代码太长撑破屏幕啦。

#include <iostream>
using namespace std;
#define MAX_N 999999 + 16

int  prime[MAX_N];			// 第i个素数
bool is_prime[MAX_N + 1];	//is_prime[i]为真的时候表示i为素数
int sieve(const int& n)
{
	int p = 0;
	fill(is_prime, is_prime + n + 1, true);
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= n; ++i)
	{
		if (is_prime[i])
		{
			prime[p++] = i;
			for (int j = 2 * i; j <= n; j += i)
			{
				is_prime[j] = false;
			}
		}
	}
	return p;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	int n;
	while (cin >> n)
	{
		cout << sieve(n) << endl;
	}
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » AOJ 0009 Prime Number 题解 《挑战程序设计竞赛》