/**
Description
素数是指只能被1和它自己整除的数，特别的，1不是素数。
比如，2,3,5,7都是素数。现给出正整数a和b(1<=a,b<=1,000,000)，
请计算a与b之间有多少个素数。输入 第一行是一个整数N，表示样例的个数。
以后每行两个整数a和b。输出 每行输出一个整数，即a和b之间的素数个数。
Sample Input
3
1 10
2 2
3 7
Sample Output
4
1
3
*/
#include
#include
#define MAX 1000001
void init();
bool markPrime[MAX];
bool isPrime(long n);
void printResult(long a,long b);
int main()
{
//将1-1000000中是素数的，以它为下标的markPrime[index]置为true、这样不用每次都去求一次
init();
//cases个测试用例，求a、b之间的素数个数、显然这里是两个闭区间
int cases;
long a,b;
scanf("%d",&cases);
while(cases--)
{
scanf("%ld%ld",&a,&b);
printResult(a,b);
}
return 0;
}
void init()
{
long i;
markPrime[0] = false;//无所谓true或者false
markPrime[1] = false;//1不是素数
for(i=2;i<=1000000;i++)
{
if(0 == i % 2 && 2 != i) //非2的偶数就直接判断了,节省时间
{
markPrime[i] = false;
}
else if(isPrime(i)) //如果是素数
{
markPrime[i] = true;
}
else
{
markPrime[i] = false;
}
}
}
bool isPrime(long n)
{
if(2 == n || 3 == n) //1、2、3都是素数 直接返回
{
return true;
}
long end = (long)sqrt(double(n)) + 1;
long i;
for(i=2;i<=end;i++)
{
if(0 == n % i)
{
return false;
}
}
return true;
}
//打印结果
void printResult(long a,long b)
{
long i;
long result = 0;
long temp;
//要考虑这种a > b的情况
if(a > b)
{
temp = a;
a = b;
b = temp;
}
for(i=a;i<=b;i++)
{
if(markPrime[i])
{
result++;
}
}
printf("%ld\n",result);
}
阅读(2015) | 评论(0) | 转发(0) |
