C - 特定のBIG範囲から素数を取得する

Question

#include <stdio.h> 
#include <math.h> 
#define UPPER_LIMIT 2147483647 
void sieve(unsigned long int n, unsigned long int primes[]); 
main() 
{ 
    unsigned long int low, up, steps; 
    unsigned long int v[UPPER_LIMIT]; 
    sieve(UPPER_LIMIT, v); 
    scanf("%ld\n",&steps); 
    for (unsigned long int i=0;i<steps;i++){ 
     scanf("%ld %ld\n",&low,&up); 
     for(unsigned long int j=low; j<up; j++){ 
      if (v[j] == 1){ 
       printf("%ld\n",j); 
      } 
     } 
    } 
} 
void sieve(unsigned long int n, unsigned long int primes[]) 
{ 
    for (unsigned long int i=0;i<n;i++){ 
     primes[i]=1; 
    } 
    primes[0]=0,primes[1]=0; 

    for (unsigned long int i=2;i<sqrt(n);i++) { 
     for (unsigned long int j=i*i;j<n;j+=i){ 
      primes[j] = 0; 
     } 
    } 
} 

私は、特定の範囲から素数を印刷する問題を解決しようとしています。 最初にscanfに、審査されるケース数を取得します。範囲はstdinの次の行で与えられます。たとえば、（1 10）の上限値はmax 2147483647になります。私は素数を見つけるためにErastostenesのSieveを使用しています。その後、私はprintfの素数を昇順にしたいと思います。残念ながら、私はランタイムエラーが発生している、私はそれを作成しようとしている非常に大きな配列のためだと仮定します。私は問題の解決策について助言が必要です。 STDINの

例：STDOUTの

1 
1 10 

例：

2 
3 
7 

Answer 1

は、グローバル最大サイズを有する素数配列を宣言する。
ベクトルを使用して素数（C++コンテナ）を格納できます。
配列のサイズは、最高でも10^7〜10^8になる可能性があります。 unsigned long int v[2147483647];この大きな配列 を宣言できません。また、この方法で問題を解決することはできません。

Answer 2

大部分の実装では、スタック上に存在するローカル変数を非常に大きなサイズで作成しようとしています。タイプがunsigned longの2G要素の場合は、8 GBまたは16 GBのいずれかを探している可能性が最も高いです。それはスタックには大きすぎます。

代わりにこの変数をグローバルとして作成します。そうすれば、スタック上には存在しませんが、実装によってはデータセクションに存在しません。

また、この配列には0と1の値しか割り当てられていないため、配列のタイプをcharに変更すると、各要素は1バイトしか使用しません。それはあなたに多くのメモリを節約します。

Answer 3

unsigned longアレイを使用して0または1のみを格納することに意味はありません。

は、あなただけが必要とするすべての情報を格納するための2147483647/8ビットを必要とするので、あなたは、せいぜい2147483647/8 + 1バイトの配列を宣言する必要があります

const unsigned int SIZE = 1 + (2147483647/8); 
unsigned char *primes = (unsigned char*)malloc(SIZE); 

：ヒープ割り当てを通じて、

const unsigned int SIZE = 1 + (2147483647/8); 
unsigned char primes[SIZE]; 

あるいはさらに良いの

アレイの初期化は次のようになります。

for (unsigned i = 0; i < SIZE ; i++){ 
    primes[i] = 1; 
} 

配列の個々のビットへのアクセスは、ビット単位の演算子>>,<<、および&で実行できます。これは大学の運動のように見えるので、これを実装することは練習として残されています。