POJ 2635 The Embarrassed Cryptographer 高精度

題意：給出一個n和L，一直n一定可以分解成兩個素數相乘。   讓你判斷，如果這兩個素數都大於等於L，則輸出GOOD，否則輸出最小的那個素數。         從1到1000000的素數求出來，然後一個一個枚舉到L，看能否被n整除，能的話就輸出BAD+改素數   都不行的話，說明兩個素數都大於等於L，輸出GOOD         AC代碼：

#include <iostream>   
#include <cstdio>   
#include <cstdlib>   
#include <cmath>   
#include <cstring>   
#include <string>   
#include <vector>   
#include <list>   
#include <deque>   
#include <queue>   
#include <iterator>   
#include <stack>   
#include <map>   
#include <set>   
#include <algorithm>   
#include <cctype>   
using namespace std;  
  
typedef long long LL;  
const int N=1000005;  
const LL II=100000000;  
const int INF=0x3f3f3f3f;  
const double PI=acos(-1.0);  
  
LL pri[N/100];  
bool num[N];  
int xx;  
char s[105];  
LL x[100];  
  
void prime()  
{  
    LL i,j;  
    int k=0;  
    memset(num,0,sizeof(num));  
    for(i=2;i<N;i++)  
    {  
        if(!num[i])  
        {  
            pri[++k]=i;  
            for(j=i;j<N;j+=i)  
                num[j]=1;  
        }  
    }  
    xx=k;  
}  
  
void toint(char *s,LL *t,int &k)  
{  
    int len=strlen(s),j;  
    char x[10]={0};  
    k=0;  
    for(;len/8;len-=8)  
    {  
        strncpy(x,s+len-8,8);  
        LL sum=0;  
        for(j=0;j<8;j++)  
            sum=sum*10+x[j]-'0';  
        t[k++]=sum;  
    }  
    if(len)  
    {  
        strncpy(x,s,len);  
        LL sum=0;  
        for(j=0;j<len;j++)  
            sum=sum*10+x[j]-'0';  
        t[k++]=sum;  
    }  
}  
  
bool modd(LL p,int len)  
{  
    int i;  
    LL xh=0;  
    for(i=len-1;i>=0;i--)  
        xh=(xh*II+x[i])%p;  
    if(xh==0)  
        return true;  
    return false;  
}  
  
int main()  
{  
    int i,j,L;  
    prime();  
    while(scanf("%s%d",s,&L))  
    {  
        if(strcmp(s,"0")==0&&L==0)  
            break;  
        int len;  
        toint(s,x,len);  
        int p=1,flag=0;  
        while(pri[p]<L)  
        {  
            if(modd(pri[p],len))  
            {  
                flag=1;  
                printf("BAD %lld\n",pri[p]);  
                break;  
            }  
            p++;  
        }  
        if(flag==0)  
            printf("GOOD\n");  
    }  
    return 0;  
}  

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;

typedef long long LL;
const int N=1000005;
const LL II=100000000;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

LL pri[N/100];
bool num[N];
int xx;
char s[105];
LL x[100];

void prime()
{
    LL i,j;
    int k=0;
    memset(num,0,sizeof(num));
    for(i=2;i<N;i++)
    {
        if(!num[i])
        {
            pri[++k]=i;
            for(j=i;j<N;j+=i)
                num[j]=1;
        }
    }
    xx=k;
}

void toint(char *s,LL *t,int &k)
{
    int len=strlen(s),j;
    char x[10]={0};
    k=0;
    for(;len/8;len-=8)
    {
        strncpy(x,s+len-8,8);
        LL sum=0;
        for(j=0;j<8;j++)
            sum=sum*10+x[j]-'0';
        t[k++]=sum;
    }
    if(len)
    {
        strncpy(x,s,len);
        LL sum=0;
        for(j=0;j<len;j++)
            sum=sum*10+x[j]-'0';
        t[k++]=sum;
    }
}

bool modd(LL p,int len)
{
    int i;
    LL xh=0;
    for(i=len-1;i>=0;i--)
        xh=(xh*II+x[i])%p;
    if(xh==0)
        return true;
    return false;
}

int main()
{
    int i,j,L;
    prime();
    while(scanf("%s%d",s,&L))
    {
        if(strcmp(s,"0")==0&&L==0)
            break;
        int len;
        toint(s,x,len);
        int p=1,flag=0;
        while(pri[p]<L)
        {
            if(modd(pri[p],len))
            {
                flag=1;
                printf("BAD %lld\n",pri[p]);
                break;
            }
            p++;
        }
        if(flag==0)
            printf("GOOD\n");
    }
    return 0;
}