yukicoder No.312 置換処理

問題はこちら
No.312 置換処理 - yukicoder

少し考えると、「2より大きな最小の約数を求めよ」という問題だとわかる
N≦10^12なのでN以下のすべての数で割ることは出来ないが、2を無視するので普通の素数判定とは微妙に違うことに注意が必要

int main(){
	long n,i;
	scanf("%ld",&n);
	for(i=3;i*i<=n;i++){
		if(n%i==0){
			printf("%ld",i);
			return 0;
			//3以上の数で割り切れたら出力して終わり
		}
	}
	//平方根まで割ってダメだったら
	//nは素数か、2*素数(←2で割れるか試してないので）
	printf("%ld",n%2==0?n/2:n);
	//2で割れるなら割ったものを、さもなくばnを出力
	return 0;
}

n≦10^12なのでi≦10^6まで調べれば良い
「2で割れるなら割る、割れないならそのまま」は「n>>1-n%2」と書けるのでまとめると

i=2;
main(long n){
	for(scanf("%ld",&n);i<1e6&&n%++i;);
	n=!printf("%ld",n%i?n>>1-n%2:i);
}

85B

2016/10/17追記
4で割れないので2で割れるなら高々1回。よって最後にnを割る処理をn&-nを使って短縮できる
i=2;
main(long n){
for(scanf("%ld",&n);i<1e6&&n%++i;);
n=!printf("%ld",n%i?n/=n&-n:i);
}
|