読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.36 素数が嫌い!

問題はこちら
No.36 素数が嫌い! - yukicoder

要するに3個以上の素数の積になってればいい
なので次のような関数fを作った

long f(long x){
	//この関数は、引数をその最小素因数で1回割った値を返す
	long i;
	if(x%2==0)return x/2;
	for(i=3;i*i<=x;i+=2)if(x%i==0)return x/i;
	return 1;
}

int main(){
	long a;
	scanf("%ld",&a);
	puts(f(f(a))>1?"YES":"NO");
	//素因数で2回割って1になっていなければ、3個以上の素因数を持つ
	return 0;
}

この方針で短縮

long a;
j,t;
main(i){
	for(scanf("%ld",&a);++t<3;a/=i>j?a:i--)for(j=sqrt(a);i++<j&&a%i;);
	a=!puts(a>1?"YES":"NO");
}

与えられる数は10^14以下なので、sqrt(a)の代わりに1e7を使って良い
ループ圧縮

long a;
t;
main(i){
	for(scanf("%ld",&a);i++<1e7&&a%i||(a/=a%i?a:i--,t^=1););
	a=!puts(a>1?"YES":"NO");
}

終了条件のチェックが2回になったので++t<2をt^=1に書き換え。xorっょぃ
いろいろ試したがfor文の長さは変わらなかった

for(scanf("%ld",&a);i++<1e7&&a%i||(a/=a%i?a:i--,t^=1););
for(scanf("%ld",&a);i++<1e7&&a%i?:(a/=a%i?a:i--,t^=1););
for(scanf("%ld",&a);i++>1e7|a%i<1?a/=a%i?a:i--,t^=1:1;);

98B


2016/10/17追記
NOを出力するべきなのは素数と半素数
素数は約数が2個で半素数は4個
特に√Nまでには1個か2個。
ということは√Nまでに約数が3個以上あるかどうかをチェックすれば良い

long a;t;
main(i){
	for(scanf("%ld",&a);a/i/i;i++)t+=a%i<1;
	a=!puts(t>2?"YES":"NO");
}

……と思ったら1ケースだけWA
累乗数の場合が考察漏れしていた。
正しくは次の通り

素数は約数が2個で半素数は3個または4個
特に√Nまでには1個か2個。
YESと出力すべきものの内、素数の立方であるもののみが√Nまでに約数を2個しか持たない
ということでaが(i*i)で割り切れるときにはtに2を加算したい…
素数の平方のときにうまくいくようにfor文の終了条件を変えて

long a,i;
main(t){
	for(scanf("%ld",&a);++i*i<a;)t+=a%(i*i)?a%i<1:2;
	a=!puts(t>4?"YES":"NO");
}

90B