問題タブ [sieve]

誰かがこの素ふるいを通して一行ずつ私を案内してくれませんか? 私は独自のふるいを開発しようとしていますが、高速なもののほとんどには、理解できない構文が含まれています (コメントした行など)。これが一種の初心者の質問である場合は申し訳ありません。また、ふるいの書き込みに役立つリンクがあれば、大歓迎です。

特定の範囲で素数を見つける問題を解決しているときに、Sigsegv エラーが発生し、間違いの場所とその修正方法を見つけることができません

C ++でふるいプログラムを書いています。しかし、すべての正当な入力に対して、プログラムは、入力がどのように変化しても、常に 4 つの素数と「2 3 5」を含む出力を生成します。コンソール経由でプログラムを実行しようとすると、二重解放または破損 (fasttop): 0x000000000063d070 *** というエラー メッセージが表示されます。ところで、私はc ++が初めてです。また、出力を正しくフォーマットしようとしていますが、ただ飛び回っているだけです。

これは望ましい形式です。

73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827

私はそれをテストしましたが、少なくとも最初の 100 個の素数で動作するようです。素数を無期限に正確に返しますか?(理論的には文字通りではありません)。

ベクトルで簡単なふるいを作ろうとしています:

私はベクターを初めて使用し、seive を使用して素数のベクターを作成しようとしていますが、どういうわけかBad_Alloc
、この悪い割り当てについて特定できる人はいますか?
前もって感謝します

エラトステネスのふるいを実装しようとしていますが、ふるい配列に関する一般的な質問があります。

私はふるいをかなりの回数 (C で) 実装しており、ふるいとしてuint8_t(out of <stdint.h>) の配列を常に使用していました。これは、ふるいにかける各数値に 8 ビットが使用されるため、1 ビットで十分なはずですが、かなりメモリ効率が悪いです。

Cでこれをどのように行うのですか？ビットの配列が必要です。uint8_t任意の型 ( 、uint16_t、uint32_t、 )の配列をほとんど作成し、uint64_tビット マスクなどを使用して単一のビットにアクセスすることができました。

パフォーマンスを低下させずにビットにアクセスするには、どのデータ型を優先し、どの操作を使用する必要がありますか?

PS: これは単なるBitArray 実装の複製ではないと思います。質問はエラトステネスのふるいに固有のものであり、その主な性質は効率的である必要があるためです (メモリ使用だけでなく、アクセスにおいても)。ふるい分けプロセスをより効率的にするために、さまざまなトリックを使用できるのではないかと考えていました...

私は最近、非常に大きな数のエラトステネスのセグメント化されたふるいのより高速な実装について読みました。

以下は、同じ実装です。

どこが間違っているのか分からないようです。おそらく長く働きすぎたのでしょう。

例えば：

sieve(4,10)戻るはずなのに戻っ[5,7] てくる[5,7,9]