数素数（http://acm.tongji.edu.cn/showproblem.php?problem_id=1010）
Problem
素数是的只能被1和它本身整除的自然数。判断一个数是素数的方法是使用2到该数的平方根的素数除它，若有能整除的则该数不是素数。 


其实是个简单问题，但对于给出的数据范围（0<M<N<1000000），总是迫使我寻找更快更省的方法。

一开始我就想找到一种数学方法，如果找到了当然是最快最省的，但是，还没找到，于是只好用笨的方法。

1、用素数的定义
  素数是的只能被1和它本身整除的自然数。那就从2到sqrt(n)进行试除，如果有一个数能整除n，那n就不是素数，否则n就是素数。
  如果不仔细想，会认为这样做已经是非常快了，其实做了很多多余的工作，以下简单分析：首先从奇偶性上看，所有的素数中只有2是偶数，也就是说几乎所有素数都是奇数，而在试除的过程中，我们还用4,6,8之类的偶数去试除，真是愚蠢到家了。同样的道理，如果3不能整除的，那所有的3的倍数也不能整除，那也不必用6,9,12去试除了。
  稍微进行改进的方法是，建立素数表，于是判断一个数n是否是素数就可以用2到sqrt(n)间的素数去除n，如果有一个素数能整除n，那n就不是素数，否则n就是素数。
  我说‘稍微’改进，实际上对于基于‘试除’的求素数方法，已经是达到了极致，同时对于n比较大的数，进行试除次数也会大大降低。以下数据可以说明问题：
n=       sqrt(n)=    直接试除次数  基于素数表试除次数
  10000    100       98            25
  50000    223       221           49
 100000    316       314           67
 500000    707       705           128
1000000   1000       998           168

代码：
#include<stdio.h>
#include<math.h>
int primes[168]=
{
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,
107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,
223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,
337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,
457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,
593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,
719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,
857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,
997};
int main()
{
    int m,n,i,j,t,count;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        count=0;
        if(m<3)
        {
            count=1;
            m=3;
        }
        else
        {
            if(m%2==0)
                m++;
        }
        for(i=m;i<=n;i+=2)
        {
            t=(int)sqrt(i);
            for(j=0;j<168&&primes[j]<=t;++j)
                if(i%primes[j]==0)
                {
                    --count;
                    break;
                }
            ++count;
        }
        printf("%d\n",count);
    }
    return 0;
}

2、用筛法
筛法描述是这样的：从自然数中（1除外）选一个最小的数，你可以大胆宣布它是素数，然后把剩下的所有自然数中是它的倍数的数全部去掉（筛去），接下来从剩下的数中再选一个最小的数重复上面的工作，这样就能求得所有的素数。

这个算法最大的弱点是需要比较大的存储空间，而时间复杂性上是比较优的，首先它只做加减法，不用试除，同时设所求范围是(2,n)，那它的复杂度是O(n)，线性复杂度。

在设计算法的时候，首先要设一个筛子v[i]，筛子初始为0，如果v[i]==1则表示i不是素数。由于筛子只取0和1，所以可以用一个bit存储。

再进一步优化（目的是使存储空间减少），对于偶数的情况不再考虑，筛子中只对奇数进行筛选。

代码：
#include<stdio.h>
#define getmap(x) (bitmap[(x-2)>>4]&bit1[(x/2-1)&7])
#define setmap(x) bitmap[(x-2)>>4]|=bit1[(x/2-1)&7]
unsigned char bit1[8]={128,64,32,16,8,4,2,1};
unsigned char bitmap[62500]={0};
int main()
{
    int i,j,m,n,count;
    for(i=3;i<=1000000;i+=2)
    {
        if(!getmap(i))
        {
            for(j=i+i+i;j<=1000000;j+=(i+i))
                setmap(j);
        }
    }
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        count=0;
        if(m<3)
        {
            count=1;
            m=3;
        }
        else if(!(m&1))
            m++;
        if(!(n&1))
            n--;
        for(;m<=n;m+=2)
            if(!getmap(m))
                ++count;
        printf("%d\n",count);
    }
    return 0;
}

评论