Codeforces 150 A. Win or Freeze

問題

ある整数に対して、二人が次のようなゲームを行う。
一人が、その数の自明でない約数を言う。（１とその数自身以外の約数）
もう一人が、前の人が言った数の自明でない約数を言う。

これを、約数が言えなくなるまで続ける。
約数を言えなくなった人の勝ちである。

最初の整数qが与えられるとき、
先手が勝つなら1を、後手が勝つなら2を出力せよ。
また、先手が勝つ場合、先手の最初の一手をどれか一つ出力せよ。
（先手が最初から勝っている場合0を出力せよ）

制約条件

q≦10^13

方針

q = p1 * p2とかける（ただし、p1,p2は素数）
ことが、後手が勝つ必要十分条件。それ以外のときは先手が勝つ。

先手は、qの約数のうち、p1*p2（p1,p2は素数）を言えばいい。
rubyで書いたらTLEした。

10^6.5のループすらまわらないとか酷い。
C++だと80msで終わるのに……

ソースコード

int main(){
	ll q;
	vector<ll> v;
	cin>>q;
	for(int i=2;(ll)i*i<=q;i++)if(q%i==0){
		int c=0;
		while(q%i==0)q/=i, c++;
		int t=min(3-(int)v.size(),c);
		rep(j,t)v.pb(i);
	}
	if(q>1&&v.size()<3)v.pb(q);
	if(v.size()==2) puts("2");
	else{
		puts("1");
		if(v.size()<2)puts("0");
		else cout<<v[0]*v[1]<<endl;
	}
	return 0;
}