c言語 ある値を境に強制終了してしまう

Question

c言語で入力されたnに対して、n<p<=2nを満たす素数pの個数を判定するプログラムなのですが、nが23200を超えたあたりでプログラムが強制終了してしまいます。いったいなぜのでしょうか？
できれば、どこをどう直したらよいのか教えていただけるとありがたいです。ちなみに素数判定はエラトステネスのふるいの考え方を用いています。

また、実行時間が長くなりすぎるということでもなさそうです。

#include <stdio.h>

int main(void){
int a[250000],i,j,n,count=0;
while(scanf("%d",&n)==1){
for(i=2;i<=2n;i++){
a[i] = 1;
}
for(i=2;i<=2n;i++){
if(a[i]==0) continue;
else{
for(j=i;ij<=2n;j++){
a[ij] = 0;
}
}
}
for(i=n+1;i<=2n;i++){
if(a[i]==1) count++;
}
printf("%d\n",count);
count = 0;
}
return 0;
}

Answer 1

こんにちは。

意外にハードな落とし穴でした。

for(j=i;ij<=2n;j++){

のi*j<=2*nなので、i*jが2*nを超えない筈なのですが、
iが46341以上になるとjも同様です。46341*46341=0x80001219ですので、通常の処理系のintの表現範囲を超えてしまうため、おかしなことになります。このような場合、負の値になる処理系が多いです。結果、i*j<=2*nの条件を満たしてしまい、かつ、a[負の値]のメモリをアクセスするため、結果として落ちているようです。

オーバーフロー怖いです。

Comments

[lkjhgfds]

分かりやすい説明ありがとうございます！
オーバーフローで逆に条件を通るということは全く思いつきませんでした、、、
この解答をもとにコードを書き変えてみます。

Answer 2

たぶん、これが原因ということはないでしょうけど、
ちとまずいところを指摘しておきます

int main(void){
int a[250000],i,j,n,count=0;

AUTO変数でintの２５００００の配列を確保するというのが無茶です
単純計算でも1MByte以上のスタック領域が必要となります
まあ、イマドキのPC上で1MByte ってのはミミクソ程度の容量でしかないでしょうけど、普通はスタック領域はそこまで確保してません。まー、リンク時のオプションをいじるなりすれば通るでしょうけどね。
いちど、

int a[250000];

int main(void){
int i,j,n,count=0;
...

と、配列宣言を外に出してやってみてください。

Answer 3

配列長が25万なのでこれ以上の添え字でアクセスしようとしているのだと思います（未検証）