入力値が100000より大きい場合、ランタイムエラーが発生する

Question

Cでエラトステネスの篩を実装しようとしています。このコードは小さな入力値に対して機能しますが、入力が特定の範囲を超えると、ランタイムエラースローされます。これは、SPOJベースの古典的なセクションの2番目の問題です。間違いは何ですか？

#include<stdio.h> 
#include<math.h> 
int prime(unsigned long int, unsigned long int); 
int main() 
{ 
    int nitem; 
    unsigned long int sn,fn; 
    scanf("%d", &nitem); 
    while(nitem) 
    { 
     scanf("%lu", &fn); 
     //printf("%d",fn); 
     scanf("%lu", &sn); 

     prime(fn, sn); 
     nitem--; 
    } 
    return 0; 
} 

int prime(unsigned long int fn, unsigned long int sn) 
{ 
    unsigned long int prim[100000]; 
    int i,j,k; 
    for(i = 0; i < 100000; i++) 
    { 
     prim[i] = 1; 
    } 

    prim[0] = 0; 
    prim[1] = 0; 
    //printf("%d", sn); 
    //printf("%d", k); 
    //printf("%d", (k <= sn)); 
    for(k = 2; k <= sqrt(sn); k++) 
    { 
    // printf("alksnc%5d", k); 
     if(prim[k] == 1) 
     { 

      for(j = 2; (k * j) <= sn; j++) 
      { 
       //printf("%d", prim[k]); 
       prim[k * j] = 0; 

      } 
     } 
    } 



    for(int i = 0; i <= sn; i++) 
    { 
     if(prim[i] !=0 && i >= fn) 
     { 
      printf("%lu\n", i); 
     } 
    } 
    printf("\n"); 

    return; 
} 

---

入力：

1 
100000 100345 

出力：

run time error 

入力：

1 
3 5 

出力：

3 
5 

Answer 1

時間と空間を無駄にしているすべての偶数として奇数だけをふるい分けることで、メモリ（2x）をより効率的に使用できます。それは動作するようにトリッキーですが、私たちのようなもの与える：

#include <math.h> 
#include <libc.h> 

#define MAX_ODD_PRIMES 1048576 

void prime(unsigned long fn, unsigned long sn) 
{ 
    unsigned char primes[MAX_ODD_PRIMES]; 

    for (unsigned long i = 0; i < MAX_ODD_PRIMES; i++) 
    { 
     primes[i] = TRUE; 
    } 

    primes[0] = 0; // preset first odd, '1' 

    for (unsigned long k = 3; k <= sqrt(sn) + 1; k += 2) 
    { 
     if (primes[k/2]) 
     { 
      for (unsigned long j = 3; (k * j) <= sn; j += 2) 
      { 
       primes[k * j/2] = FALSE; 
      } 
     } 
    } 

    if (fn <= 2) 
    { 
     printf("2\n"); 
     fn = 3; 
    } 

    for (unsigned long i = fn/2; i * 2 + 1 <= sn; i++) 
    { 
     if (primes[i]) 
     { 
      printf("%lu\n", i * 2 + 1); 
     } 
    } 
} 

例

> ./a.out 
1 1999900 2000000 
1999957 
1999969 
1999979 
1999993 
> 

Answer 2

1）アレイの範囲エラーを。入力2によりコード

for (j = 2; (k * j) <= sn; j++) { 
    if (k * j >= 100000) { 
     printf("Out of range %d %d\n", k, j); 
     exit(1); 
    } 
    prim[k * j] = 0; 

    } 
} 

を変化させることにより

、アレイ（VLA）を使用して100000
出力

Out of range 2 50000 

タスクに寸法決め、これが回避されます。他にも多くの最適化が可能です。配列malloc()も考えてみてください。

void prime(unsigned long int fn, unsigned long int sn) { 
    unsigned long int prim[sn + 1]; 

2）int prime()結局return something;が期待さreturn;を行います。変更機能を提案するvoid prime()

int prime(unsigned long int fn, unsigned long int sn) { 
    unsigned long int prim[100000]; 
    ... 
    printf("\n"); 
    return; 
}