数学#素数筛法 HDU 4548&POJ 2689

找素数本来是很简单的问题，但当数据变大时，用朴素思想来找素数想必是会超时的，所以用素数筛法。

素数筛法 打表伪代码（用prime数组保存区间内的所有素数）：

          void isPrime()

               vis[]数组清零；//vis[]数组用于标记是否已被检验过

               prime[]数组全赋初值false；//prime[]数组从下标0开始记录素数

               for i = 2 to MAXN (i++)

                      if 数i未被检验过

                            prime[tot++]=i;

                            for j = i*i to MAXN (j+=i) //j是i的倍数

                                     标记该数已被否定，不是素数 //vis[j]=1;

 

最先做的是hdu的美素数，要求数n本身就是素数，而且n的各位数之和亦是素数，先打表，再进行素数筛法；函数cnt（）中用到了dp思想；

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1000005;
int ans[MAXN];
bool prime[MAXN];

void isPrime()
{
    memset(ans,0,sizeof(ans));
    memset(prime,true,sizeof(prime));
    prime[0]=prime[1]=false;
    for(int i=2;i<MAXN;i++)
    {
        if(!prime[i])
            continue;
        for(int j=i*2;j<MAXN;j+=i)
            prime[j]=false; //point!
    }
}

int addWei(int n)
{
   int sum=0;
   while(n)
   {
       sum+=n%10;
       n/=10;
   }
   return sum;
}

void cnt()
{
    ans[0]=ans[1]=0;
    for(int i=2;i<MAXN;i++)
    {
        if(prime[i]&&prime[addWei(i)])
            ans[i]=ans[i-1]+1;
        else ans[i]=ans[i-1];
    }
}

int main()
{
    int t,l,r;
    isPrime();
    cnt();
    scanf("%d",&t);
    for(int ca=1;ca<=t;ca++)
    {
        scanf("%d %d",&l,&r);
        printf("Case #%d: %d
",ca,ans[r]-ans[l-1]);
    }
    return 0;
}

---

第二道是poj上一道二次筛法的题目，如何进行二次素数筛，见下面代码：

参考此博：http://blog.csdn.net/a601025382s/article/details/12111297

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
//这个解法比较慢，但是好理解，其他快的暂时还理解不了
const int N=47000;

ll l,u,prime[N];
int tot;
int vis[N],ans[10000005];

void isPrime()
{
    tot=0;
    memset(vis,0,sizeof(vis));
    memset(prime,0,sizeof(prime));
    for(ll i=2;i<N;i++)
    {
        if(!vis[i])
        {
            prime[tot++]=i;
            for(ll j=i*i;j<N;j+=i)
                vis[j]=1;
        }
    }
}

int main()
{
    ll pre,maxn,u1,v1,minn,u2,v2;
    int flag;

    isPrime();
    while(~scanf("%I64d%I64d",&l,&u))
    {
        if(l<=1)
            l=2;//1既不是素数，也不是合数

        //二次筛选
        memset(ans,0,sizeof(ans));
        for(int i=0;i<tot&&prime[i]<=u;i++)
        {
            ll t=l/prime[i]+(l%prime[i]>0);
            if(t==1) t++;
            for(ll j=t*prime[i];j<=u;j+=prime[i])
                ans[j-l]=1;
        }

        maxn=-2*N;minn=2*N;
        flag=0;
        for(ll i=l;i<=u;i++)
        {
            if(!ans[i-l])
            {
                flag++;
                if(flag>1)
                {
                    int temp=i-pre;
                    if(temp>maxn)
                    {
                        maxn=temp;
                        u1=pre;v1=i;
                    }
                    if(temp<minn)
                    {
                        minn=temp;
                        u2=pre;v2=i;
                    }
                }
                pre=i;
            }
        }
        if(flag>1)
            printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.
",u2,v2,u1,v1);
        else printf("There are no adjacent primes.
");
    }
    return 0;
}