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); } }