SPOJ Prime Generator

SPOJ   Prime Generator
   题目意思：给定两个正整数m,n,(1<=m<=n<=10^9,n-m<=100000),求m到n之间的所有素数。
  方法1:对区间[m,n]内的每一个数进行miller_rabin素数测试(时间复杂度较高,约为1.37s~4.6s)
  代码实现所需的算法有：
① 产生[0,1]及[0,m-1]之间的随机数函数Random(),Random(m)
② 手写乘法取模函数mul_mod()
③ 二分求幂a^b%n函数pow_mod(a,b,n)
④ Miller_rabin素数测试算法

#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <iostream>
using namespace std;
typedef long long lld;
//产生[0,1]之间的随机数
double Random()
{
    return (double)rand()*1.0/RAND_MAX;
}
//产生[0,m-1]之间的随机数
lld Random(lld m)
{
    return (lld)(Random()*(m-1)+0.5);
}
//手写乘法取模，防止64位溢出
//注意此函数最好是在用__int64还会溢出的情况下使用
//否则在其它情况下会增加程序的时间复杂度
//如在SPOJ Prime Generator题目中使用就TLE，去掉就AC啦
//同时也仍需要注意在实现此函数应少用取模运算%，因为这也会增加
//程序的时间复杂度，在某些题目中也会TLE，如FZU A^B%C
lld mul_mod(lld a,lld b,lld n)
{
    lld res=0,temp=a%n;
    while(b)
    {
        if(b&1)
        {
            res+=temp;
            if(res>=n)  res-=n;
        }
        temp<<=1;
        if(temp>=n) temp-=n;
        b>>=1;
    }
    return res;
}
//求a^n%p
//注意在SPOJ Prime Generator中需注释mul_mod
//如果a*b%n用__int64仍会溢出则必须用mul_mod
lld pow_mod(lld a,lld n,lld p)
{//二分求幂
    lld res=1,half=a%p;
    while(n)
    {
        if(n&1) res=res*half%p;//mul_mod(res,half,p);
        half=half*half%p;//mul_mod(half,half,p);
        n>>=1;
    }
    return res;
}
//判断n是否是合数，如果是则返回true,否则false
/*bool witness(lld a,lld n)
{//a^(n-1)=1 (mod n)
    lld u=n-1;
    lld t=0;
    while((u&1)==0)
    {//计算n-1=u*(2^t),其中t>1,u为奇数
        u>>=1;
        t++;
    }
    lld x=pow_mod(a,u,n);
    for(int i=1;i<=t;i++)
    {
        lld k=mul_mod(x,x,n);
        if(k==1&&x!=1&&x!=n-1)  return true;
        x=k;
    }
    if(x!=1)    return true;
    return false;
}*/

bool witness(lld a, lld n)
{
    lld m = n - 1;
    lld q = 0;
    while((m&1) == 0)
    {
        q ++;
        m >>= 1;
    }
    lld x = pow_mod(a, m, n);
    if (x == 1 || x == n-1) return false;//n可能为素数
    while(q --)
    {
        x = x * x % n;
        if (x == n-1) return false;
    }
    return true;//n一定是合数
}


bool miller_rabin(lld n,lld s)
{//此函数的时间复杂度可以通过调整s的大小来调节，一般s>=3
    if(n==2||n==3)  return true;
    if(n<=1||n%2==0||n%3==0)    return false;
    for(int i=1;i<=s;i++)
    {
        lld a=Random(n-1)%(n-1)+1;
        if(witness(a,n))    return false;
    }
    return true;
}
int main()
{
    int t;
    lld m,n;
    srand(time(NULL));
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&m,&n);
        for(lld i=m;i<=n;i++)
        {
            if(miller_rabin(i,20))  printf("%lld\n",i);
        }
        printf("\n");
    }
    return 0;
}

方法二：这题使用的是标准筛法的一个修改版本。如果用普通的筛法，对[2, n]内的每个数进行排查，明显不是高效的，会使用很多的时间和空间。然而，我们可以发现，[0, n]内没有一个合数的因子大于floor(sqrt(n))。所以，我们只需要把[2, sqrt(n)]，即[2, 31622]以内的素数筛出来。然后，对于每个询问[a, b]，使用预先筛好的素数进行第二次筛选，最后得到[a, b]内的素数，输出。
涉及的算法：
① 素数筛选法及二次筛选给定区间[m,n]内的素数
代码1：

#include <iostream>
#include <cstdio>
#include <memory.h>
#define MAXN 32000
using namespace std;
bool a[MAXN];
int prime[MAXN];//储存2~32000内所有的素数
int num;//记录素数的个数
int m,n;
int p[100010];
void getPrime1()
{//素数筛选法 
    memset(a,0,sizeof(a));// 初始进假设所有数均为素数
    a[0]=a[1]=1;
    for(int i=2;i*i<=MAXN;i++)
    {
        if(!a[i])
        for(int j=i;j*i<=MAXN;j++)
        a[j*i]=1;
    }
    num=0;
    for(int i=0;i<MAXN;i++)
    {
        if(!a[i])   {prime[num++]=i;
        //cout<<i<<" ";
        }
    }
    //cout<<endl;
}
void getPrime2()
{//二次筛选把[m,n]内的合数删除 
    memset(p,0,sizeof(p));
    for(int i=0;i<num&&prime[i]<=n;i++)
    {
        //cout<<prime[i]<<" ";
        int k=m/prime[i];
        for(int j=k;j*prime[i]<=n;j++)
        {
            if(j!=1&&j*prime[i]>=m) p[j*prime[i]-m]=1;
        }
    }
    for(int i=0;i<=n-m;i++)
    {
        if(!p[i]&&i+m!=1)   printf("%d\n",i+m);
    }
}
int main()
{
    int t;
    num=0;
    getPrime1();
    scanf("%d",&t);
    bool flag=false;
    while(t--)
    {
        if(flag)    printf("\n");
        flag=true;
        scanf("%d%d",&m,&n);
        getPrime2();
    }
    return 0;
}