Chinaunix首页 | 论坛 | 博客
  • 博客访问: 506070
  • 博文数量: 65
  • 博客积分: 1158
  • 博客等级: 少尉
  • 技术积分: 1261
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-18 22:07
文章分类

全部博文(65)

文章存档

2016年(1)

2014年(2)

2013年(9)

2012年(53)

分类: C/C++

2012-09-21 16:37:21

/**
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);
}



阅读(1693) | 评论(0) | 转发(0) |
0

上一篇:无向图的关节点

下一篇:成绩排名

给主人留下些什么吧!~~