4

C++ でビット操作を介して素数を見つけるにはどうすればよいですか?

4

4 に答える 4

14

これを行う方法は、ビットセットを通常のように数値表現と見なすのではなく、数値のリストで考えることだと思います。だからビットセット

1111

は、1、2、3、および 4 の数字を表します。ここで、「1」が素数を表し、「0」が素数ではないことを表すとすれば、次のようにふるいを作成できます。

すべてのビットを 1 に設定します (1 ～ 16 の整数を表す 16 ビットを使用します)

1111 1111 1111 1111

1 が素数でないことはわかっているので、0 に設定しています。

0111 1111 1111 1111

ここで、次に遭遇する「1」が素数を表すことはわかっていますが、その数のすべての倍数は定義により素数ではないため、次の「1」はそのままにして、その倍数をすべて「0」に設定します。次の「1」は数字の 2 を表すため、2 ビットごとにゼロにします。

0110 1010 1010 1010

他の方法に対するこの方法の利点は、残りのビットをトラバースするときに、ビットが 2 で割り切れるかどうかを確認するために各ビットをチェックする必要がないことです (したがって、このような方法if i % 2 == 0は必要ありません)。インデックスを 2 ずつインクリメントし続けるだけで、常に非素数に到達することがわかっています。

ここで、次に遭遇する「1」で同じことを繰り返すだけです (次の素数は、識別した最後の素数 2 から始まります)。下の数字のどれでも割り切れないので、素数であることはわかっています。その倍数はすべて素数であることがわかっているので、3 番目の位置にあるので、後続の 3 ビットごとに「0」に設定します。それらのいくつかは、2 の倍数でもあるため、既に「0」になっています。問題ありません。「0」のままにしておいてください。

0110 1010 0010 1000

次に遭遇する「1」は 5 番目のビットです。これで、最後まで続けることができますが、5 は最初のビット数の平方根よりも大きいため、これ以上合成を見つけることができないことがわかっているので、これで完了です。

もう少し検索した後、Deitel & Deitel のC++ How to Programで本当に良い実装例を見つけました。また、アルゴリズムとコードの適切な説明も提供します。

于 2009-05-22T17:12:39.380 に答える
12

ビットセットを使用して素ふるいを実装してみてください。アルゴリズムは、特定の数が素数であるかどうかを格納するだけで済みます。それには1ビットで十分です。

于 2009-05-22T16:26:21.173 に答える
0

わからない場合、他の人から回答を得ることは一種の不正行為ですよね? あなたが知らない男に教えてください。面接ですべての質問を知らなくても大丈夫です。「わからない」と言うよりも、不正行為やコピーで捕まる方がはるかに悪いようです。素数が何であるかをどのように知っているかを説明し、素数のいくつかの性質を説明し、ビット演算について知っていることを説明してください. これらのことを知らないと、この仕事は向いていないのではないでしょうか?

于 2009-05-22T16:28:17.867 に答える
-1

この c# コードを見つけました。よく読めると思います。

using System;
using System.Collections.Generic;
using System.Text;

namespace eratosthenes
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 100;
            bool[] primes = new bool[n];
            for (int i = 2; i < n; i++) {
                primes[i]=true;
            }

            for (int i = 2; i < n; i++) {
                if (primes[i] == true) {
                    for (int j = i * i; j < n; j=j+i)
                    {
                        primes[j] = false;
                    }
                    Console.WriteLine(i);
                }
            }
            Console.ReadLine();
        }
    }
}

ドイツのウィキブック ページへのリンク。

于 2009-05-22T16:27:39.973 に答える