char prime[500000]; を1で初期化して、

n=2 → √500000と動かして
prime[n]==1ならば、nの倍数の配列すべてに0を入れる

するとprimeが1のもの