筛法 - 一片小天空

http://acm.fzu.edu.cn/problem.php?pid=1563

Prime Numbers

Time Limit:2s	Memory limit:32M
Accepted Submit:156	Total Submit:624

Compute the number of prime numbers in a given interval.

A prime number is an integer p greater than 1 whose only positive divisors are 1 and p.

Input

The first line contains the number of test cases T (T<=1000).

Each test case contains a single line with two numbers separated by a single space: a and b, 2 <= a <= b <= 1000000.

Output

For each test case output a single line, containing the number of primes between a and b inclusive.

Sample input

2
            2 7
            3 1000000

Sample output

4
            78497

#include<iostream>

using namespace std;

int a[1000001]={0};

int main()

{

for(int i=4; i<=1000000; i+=2)//把偶数全部赋值为1，即排除偶数

{

a[i]=1;

}

for(int n=3; n<=1000; n++)//从3开始，只需要到1000就够了

{

if(a[n]) continue;

for(int i=n*n; i<=1000000; i+=n*2)//感觉还是有做了很多无用功，但不想在优化了，感觉能力有限，(*^__^*) 嘻嘻……

{

a[i]=1;

}

for(int i=2,j=2; i<=1000000; i++ )//设2为第二个素数，依次类推，设为第二个素数主要是因为把不是素数的数设为1了，这里就不能赋值为1了

{

if(!a[i]) a[i]=j++;

}

int t;

cin>>t;

while(t--)

{

int s=0,m,n;

cin>>m>>n;

while(a[m++]==1);//这里找到比m大的第一个素数

while(a[n--]==1);//找到比m小的第一个素数

s=a[n+1]-a[m-1]+1;//OK了

cout<<s<<endl;

}

return 0;

}

一道很郁闷的题目，感觉筛法已经很快了，不可能超时啊！！可事实确实不停地超时超时，一直优化一直优化，依然还是超时，后来无意间看到一句话，计算一共有几个素数的时候应该是用O（1）的时间，这下才醒悟过来，于是才得到现在这样的代码，0.32s，还行。之前只是简单的从m扫到n，查看期间有几个素数而已。

posted on 2008-11-10 22:19 我来我往阅读(73) 评论(0) 编辑收藏引用所属分类: acm

常用链接

留言簿(1)

随笔分类(2)

随笔档案(4)

文章分类(1)

文章档案(1)

搜索

最新评论

阅读排行榜

评论排行榜

只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 BlogJava 知识库博问管理