PKU 2635 The Embarrassed Cryptographer

http://poj.org/problem?id=2635
(4<=k <=10^100)となるkと、(2<=l<=10^6)となるlが与えられる。
この時、l未満の素数でkの因数となるものがあるかどうかを判定するという問題。

javaに頼らないと解けないかと思いましたが、あまりが0であるかどうかを確認すればいいので、4桁ごとに区切ってあまりを計算しました。

未満と以下を読み間違えてたり、オーバーフローやらなんやらで結構WAをもらいました。

bool pr[1000001];
int npr[1000000],pos;

main(){
  pr[0]=pr[1]=true;
  for(int i=2;i<1000001;i++){
    if(pr[i])continue;
    for(int j=i*2;j<1000001;j+=i)pr[j]=true;
  }
  rep(i,1000001)
    if(pr[i]==false)npr[pos++]=i;
  
  string in;
  int l;
  while(cin>>in>>l,l){
    vector<int> num;
    int t=0;
    reverse(ALL(in));
    int sz=SZ(in);
    rep(i,sz){
      int base=1;
      rep(j,4){
        if(i<sz)t+=(in[i++]-'0')*base;
        base*=10;
      }
      --i;
      num.pb(t);
      t=0;
    }
    reverse(ALL(num));
    bool ok=true;
    rep(i,pos){
      if(npr[i]>=l)break;
      ll mo=0;
      rep(k,SZ(num)){
        mo=(mo*10000+num[k])%npr[i];
      }
      if(mo==0){
        ok=false;
        cout<<"BAD "<<npr[i]<<endl;
        break;
      }
    }
    if(ok)cout<<"GOOD"<<endl;
  }
}