問題はこちら
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