yukicoder No.371 ぼく悪いプライムじゃないよ

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