問題はこちら
No.371 ぼく悪いプライムじゃないよ - yukicoder
L~Hのすべての数の最小素因数を求めているとTLE
そこで、「pを最小素因数とする合成数がL~Hの中にあるか」を調べていく
合成数Nの最小素因数がpならp*p≦Nなので、そのような素数pの候補は√H=10^5以下
よって大きな素数から順に試せば良い
10^5以下の素数は9592個あるらしい
int main(){ long p[10000],L,H,i,j,k,s; s=0; //10^5以下の素数を列挙 for(i=2;i<100000;i++){ for(j=0;j<s&&i%p[j];j++); if(j==s)p[s++]=i; } scanf("%ld%ld",&L,&H); for(i=s-1;;i--){ //p[i]を最小素因数とする数があるか調べる if(p[i]*p[i]>H)continue; //p[i]*p[i]>Hなら、H以下の数は必ずP[i]未満の素因数を持つ for(j=H/p[i];p[i]*j>=L;j--){ //H以下のp[i]の倍数を大きい方から調べる for(k=0;k<i&&j%p[k];k++); if(k==i){printf("%ld",j*p[i]);return 0;} //p[i]より小さな素因数を持たなければそれが答え } } }
3重ループの1番外で前半のsを再利用し、continue文は2番目のfor文の条件にまとめる
long p[9999],L,H,j,s; main(i){ for(;++i<1e5;j*j>i?p[s++]=i:0)for(j=1;++j*j<=i&&i%j;); for(scanf("%ld%ld",&L,&H);s--;){ for(j=H/p[s];j>=p[s]&&j*p[s]>=L;j--){ for(i=0;i<s&&j%p[i];i++); if(i==s)exit(!printf("%ld",p[s]*j)); } } }
ポインタを使いつつもうちょい縮める
long p[9999],L,H,j,*q=p; main(i){ for(;++i<1e5;j*j>i?*q++=i:0)for(j=1;i/++j/j&&i%j;); for(scanf("%ld%ld",&L,&H);q--;) for(j=H/ *q;j>=*q&&*q*j/L;p+i-q?j--:exit(!printf("%ld",j**q))) for(i=0;p+i-q&&j%p[i];i++); }
前半のfor文を圧縮
for(;++i<1e5;j*j>i?*q++=i:0)for(j=1;i/++j/j&&i%j;); //↓形式的な書き換え(これでも通る) for(;i/++j/j&&i%j?:(j*j>i?*q++=i:0,j=++i<1e5);); //↓条件をぐっと睨む for(;j=++j*j>i?*q++=i,++i<1e5:i%j?j:++i<1e5;); //最初はi=1,j=0から始まり、最後の部分が実行されi=2,j=1になる //その後は通常と同じ
ということで
long p[9999],L,H,j,*q=p; main(i){ for(;j=++j*j>i?*q++=i,++i<1e5:i%j?j:++i<1e5;); for(scanf("%ld%ld",&L,&H);q--;) for(j=H/ *q;j>=*q&&*q*j/L;p+i-q?j--:exit(!printf("%ld",j**q))) for(i=0;p+i-q&&j%p[i];i++); }
199B