PKU 3048 Max Factor
http://poj.org/problem?id=3048
簡単な問題かと思いきや、ひっかかりました。
n個の数字が与えられる。
この数字のうち、最も大きな素数を約数に持つ数字を答えろというような問題。
ただし、素数は1とその数自身以外に約数を持たないかずとする。
1を素数に入れなかったせいで2回くらいWAりました。
bool pr[20001]; int npr[10000]; int prnum; main(){ pr[0]=pr[1]=true; for(int i=2;i<20001;i++){ if(pr[i])continue; for(int j=i*2;j<20001;j+=i)pr[j]=true; } rep(i,20001)if(!pr[i])npr[prnum++]=i; int n; cin>>n; int ans=1,maxp=1; while(n--){ int in; cin>>in; if(in==1)continue; int t=in; int tmp=0; rep(i,prnum){ if(t<npr[i])break; if(t%npr[i])continue; tmp=npr[i]; while(t!=0 && t%npr[i]==0)t/=npr[i]; } if(tmp>maxp){ maxp=tmp; ans=in; } } cout<<ans<<endl; }