yukicoder No.106 素数が嫌い！2

問題はこちら
No.106 素数が嫌い！2 - yukicoder

a[i]にiがいくつの素因数を持つかを保存していく

int main(){
	int a[2000010]={},n,k,i,j,s;
	scanf("%d%d",&n,&k);
	for(i=2;i<=n;i++){
		if(!a[i])for(j=i;j<=n;j+=i)a[j]++;
		//もしa[i]が0なら、iは素数なので、iの倍数全てに1を加算
	}
	s=0;
	for(i=2;i<=n;i++)s+=a[i]>=k;
	//k以上の物を数える
	printf("%d",s);
	return 0;
}

ループ変数iがx以上になればそれ以降a[x]の値をいじることはないので、sのカウントをループ内に入れることができる

s=0;
for(i=2;i<=n;i++){
	if(!a[i])for(j=i;j<=n;j+=i)a[j]++;
	s+=a[i]>=k;
}

if文が邪魔なのでループを逆にする

for(i=2;i<=n;s+=a[i++]>=k)for(j=n/i*i;!a[i];j-=i)a[j]++;

あとはiの初期化を工夫して

a[1<<22];s,n,k,j;main(i){for(scanf("%d%d",&n,&k);i++<n;s+=a[i]>=k)for(j=n/i*i;!a[i];j-=i)a[j]++;s=!printf("%d",s);}
//jへの代入をうまく利用
a[1<<22];s,n,k,j;main(i){for(scanf("%d%d",&n,&k);j=i++<n?n/i*i:!printf("%d",s);s+=a[i]>=k)for(;!a[i];j-=i)a[j]++;}

114B
ループ圧縮はうまくできなかった

a[1<<22];s,n,k,j;main(i){for(j=scanf("%d%d",&n,&k);a[i]?s+=a[i]>=k,j=i++<n?n/i*i+i:!printf("%d",s-!~-k):++a[j-=i];);}