Prime Ai Algo
对埃拉托斯特尼筛法进行总结，听名字数学味道就很重。
这个算法，我当时面百姓网的时候遇到了，而且我在C语言助教期中考试答题第一题就是这个，当时小胖帮我改估计只有i*i的才拿满分，
由于改的过于苛刻，差点出了教学事故。
通过筛选i(2….n/2(sqrt(n)))的倍数来去掉合数，这里面主流的分成两个写法，一种是
筛选2*i开始
P[1..n]=0//all primes initially
for(i=2=>n/2, i++)
{
if(!P[i])
{
for(j=2i->n, j+=i) P[j]=1;
}
}
筛选i*i开始
P[1..n]=0//all primes initially
for(i=2=>sqrt(n), i++)
{
if(!P[i])
{
for(j=i*i->n, j+=i) P[j]=1;
}
}
筛法时间复杂度当时雅虎群里一哥们说是nlglgn, 并发了一个wiki证明过程，几乎线性吧，上述两种第二种测试比较快，通过分析也是
显然的，举例6在2i方法里会筛两次，3i(2), 2i(3)， 而后者只会出现一次，i(2)(i+1), 也即后者保证第二个数比第一个数大，这样不重复筛，
但是渐进时间复杂度并没有大的改善，应该是常数项的改进。
之前fb hackerup round1第一题是一道求[a,b]以内素因子个数为k的数的个数，这道题目其实是算素因子，我却没有想到好的算法，暴力搞，结果超时了，
没跑出来，后来看了G神代码，发现居然是埃式筛法，原来埃式筛法还可以算素因子个数，我果然思考的太少，只知道举一不会反三，只会这题，不会这一系列的题目
，但是必须用2i的埃式筛法，第二种错误，例如6有2 3两个素因子，在2i 版本里，出现两次刚好筛了2 3两个素数的倍数，而ii里面，只会2(2+1)里面出现一次，漏掉3的两倍这样
一个素数因子3。当时在美国最后一天，住在姚立夫家里，姚立夫真是慷慨，让我睡床，他睡沙发。可能由于时差的关系，晚上很晚就困，早上6点多就醒来，FB上闲逛，发现hackerup，还有一点时间结束，于是打算看一题。
所以要学会举一反三，再次膜拜G神，太厉害了。
总结就是，如果算一定范围内的素数，用ii 2i都可以，但是ii更快一些，但只是常数级别上，而算素因子个数只能2i.另外要学会多思考，多举一反三。
题目：https://www.facebook.com/hackercup/problems.php?pid=582396081891255&round=344496159068801
核心代码：
void F(int n)//Print primes in [1..n]
{
memset(P, 0, sizeof(P));
//fill(P, P+maxn, 1);
for(int i=2;i<=n;i++)
{
if(!P[i])
{
for(int j=2*i;j<=n;j+=i)
P[j]++;
}
}
//for(int i=2;i<=n;i++) if(!P[i]) cout<<i<<" ";
}