PKU 2191 Mersenne Composite Numbers

http://poj.org/problem?id=2191
整数kが与えられる。(k<=63)
この時に、2^p-1 (p<=k でpは素数)で表される数のうち、合成数のものを素因数分解して表示しろというような問題。

もし素因数分解できるなら、そこまで大きくない数に分解されるようなので、愚直にやる。若干埋め込み。

void di(ll p){
  ll in=(1LL<<p)-1;
  bool pr=false;
  for(ll i=2;i*i<=in;i++){
    if(in%i)continue;
    while(in%i==0){
      if(pr)cout<<" * ";
      pr=true;
      cout<<i;
      in/=i;
    }
  }
  if(in>1)
    cout<<" * "<<in;

  cout<<" = "<<(1LL<<p)-1<<" = ( 2 ^ "<<p<<" ) - 1"<<endl;
}

bool np[100];

main(){
  np[11]=np[23]=np[29]=np[37]=np[41]=np[43]=np[47]=np[53]=np[59]=true;
  int n;
  cin>>n;
  rep(i,n+1){
    if(np[i])di(i);
  }
}