SPOJ Prime Generator

SPOJ   Prime Generator
2つの正の整数m,n,(1<=m<=10^9,n-m<=10000000)を与え,mからnの間のすべての素数を求める.
方法1:区間[m,n]内の各数をmiller_rabin素数試験(時間的複雑度が高く、約1.37 s~4.6 s)
コード実装に必要なアルゴリズムは次のとおりです.
①[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
",i);
        }
        printf("
");
    }
    return 0;
}

方法2:この問題は標準ふるい法の修正バージョンを使用している.通常のふるい法で[2,n]内の各数を調べると,明らかに効率的ではなく,多くの時間と空間が用いられる.しかしながら,[0,n]内にfloor(sqrt(n))より大きい合数の因子は1つもないことが分かった.したがって,[2,sqrt(n)],すなわち[2,31622]以内の素数をふるい出すだけである.そして、各問合せ[a,b]について、予めふるった素数を用いて2回目のスクリーニングを行い、最後に[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
",i+m);
    }
}
int main()
{
    int t;
    num=0;
    getPrime1();
    scanf("%d",&t);
    bool flag=false;
    while(t--)
    {
        if(flag)    printf("
");
        flag=true;
        scanf("%d%d",&m,&n);
        getPrime2();
    }
    return 0;
}