3

エラトステネスのふるい法を使用して、最大20億の素数をリストしてみました。これが私が使ったものです！

私が直面している問題は、1000万を超えることができないということです。試してみると、「セグメンテーション違反」と表示されています。インターネットで検索して原因を調べました。一部のサイトによると、これはコンパイラ自体のメモリ割り当ての制限です。ハードウェアの制限だという人もいます。4GBのRAMがインストールされた64ビットプロセッサを使用しています。それらをリストアップする方法を教えてください。 

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000000
long int mark[MAX] = {0};

int isone(){
   long int i;
   long int cnt = 0;
   for(i = 0; i < MAX ; i++){
      if(mark[i] == 1)
         cnt++;
   }
   if(cnt == MAX)
      return 1;
   else
      return 0;
}



int main(int argc,char* argv[]){
   long int list[MAX];
   long int s = 2;
   long int i;
   for(i = 0 ; i < MAX ; i++){
      list[i] = s;
      s++;
   }
   s = 2;
   printf("\n");

   while(isone() == 0){
      for(i = 0 ; i < MAX ; i++){
         if((list[i] % s) == 0)
            mark[i] = 1;
      }
      printf(" %lu ",s);
      while(mark[++s - 2] != 0);
   }

   return 1;
}
4

2 に答える 2

6

long int mark[1000000]スタック割り当てを行いますが、これはその量のメモリに必要なものではありません。long int *mark = malloc(sizeof(long int) * 1000000)代わりに、ヒープメモリを割り当ててみてください。これにより、最大1Milの配列要素を超えることができます。

freeもう使用しない場合は、メモリに覚えておいてください。mallocまたはfreeがわからない場合は、Linux端末を介してman 3 mallocおよびman 3 free任意のLinux端末で利用できる機能のマンページ（マニュアル）をお読みください。（または、グーグルすることもできますman malloc）

編集：calloc(1000000, sizeof(long int))0で初期化された配列を持つようにします。これはおそらくより良いでしょう。

さらに、配列のすべての要素をビットマスクとして使用して、sizeof（long int）バイトごとではなく、ビットごとに1つのマークを格納できるようにすることができます。uint32_t配列要素のように固定幅の整数型を使用してから、n番目の要素を1に設定するのではなく、配列の'番目の要素の(n % 32)'番目のビットを1に設定することをお勧めします。(n / 32)

i次を使用して、整数のn番目のビットを設定できます。

uint32_t i = 0;
i |= ((uint32_t) 1) << n

0からカウントを開始すると仮定します。

これにより、数値nのuint32_tビットマスク配列に対するset操作が行われます。

mask[n / 32] |= ((uint32_t)1) << (n % 32)

これにより、32ビットタイプのメモリを99％以上節約できます。楽しんでください：D

ここで使用するもう1つのより高度なアプローチは、素数分解です。これは、基本的に、2、3、および5（および場合によってはそれ以上）を素数として事前に宣言し、マスク配列でこれらの1つで割り切れない数値のみを使用することを意味します。 。しかし、それは本当に高度な概念です。

ただし、Cで2と3のホイール因数分解を約15行のコード（プロジェクトオイラー用）で記述したので、このようなものを効率的に実装できます;）

于 2013-01-08T09:21:59.023 に答える
2

最も直接的な改善は、奇数を表すビットに切り替えることです。したがって、M=20億の数値、つまり10億のオッズをカバーするには、1000/8 = 1億2500万バイト=〜120 MBのメモリが必要です（calloc関数を使用して、ヒープに割り当てます）。

位置のビットiは数値を表し2*i+1ます。したがって、素数の倍数をマークするときp、つまりp^2, p^2+2p, ..., M、p^2=(2i+1)^2=4i^2+4i+1位置でビットで表され、その上j=(p^2-1)/2=2i(i+1)の次の倍数はp、位置の増分でp=2i+1、

for( i=1; ; ++i )
  if( bit_not_set(i) )
  {
      p=i+i+1;
      k=(p-1)*(i+1);
      if( k > 1000000000) break;
      for( ; k<1000000000; k+=p)
         set_bit(k); // mark as composite
  }
// all bits i>0 where bit_not_set(i) holds, 
// represent prime numbers 2i+1

次のステップは、キャッシュサイズに収まる小さなセグメントでの作業に切り替えることです。これは物事をスピードアップするはずです。値が20億の平方根、つまり44721未満の素数用に、メモリ領域を予約するだけで済みます。

まず、この小さな領域をふるいにかけて、そこに素数を見つけます。次に、これらの素数を別のint配列に書き込みます。次に、この素​​数の配列を使用して各セグメントをふるいにかけ、見つかった素数をstdoutなどに出力します。

于 2013-01-08T11:01:47.167 に答える