放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

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 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机