6

100 万個の素数を出力するための質問が 1 つあります。そのためのJavaプログラムを作成しました..現在、計算に約1.5分かかります..私のソリューションはそれほど効率的ではないと思います。以下のアルゴリズムを使用しました。

  • 最初に素数リストに 1 2 3 を追加する
  • チェックする番号の最後の桁を計算する
  • 数字が 0 、 2 または 4 または 6 または 8 であるかどうかを確認してから、数字をスキップします
  • それ以外の場合は、数値の平方根を計算します..
  • 2 から始まる数の平方根までの数の割り算
  • 数が割り切れる場合はその数をスキップし、それ以外の場合は素数リストに追加します

他のいくつかのソリューションも読みましたが、良い答えが見つかりませんでした。これを計算するためのおおよその最小時間と、アルゴリズムをより効率的にするために必要な変更を理想的に提案してください。

4

10 に答える 10

15

リストに 1 を追加した場合、あなたの答えはすでに間違っています :)

とにかく、エラトステネスのふるいから始めるべきです。信じられないほどシンプルで非常に効率的です。

ふるいの概念とその仕組みに慣れたら、少し複雑ですが明らかにより効率的なAtkin のふるいに進むことができます。

于 2012-11-15T19:08:59.107 に答える
5

重要事項:

  1. すべての偶数をスキップします。5個から始めて、一度に2個追加してください。
  2. 1は素数じゃない…
  3. 数の平方根までのすべての素数の mod を見つけることによって、数をテストします。素数以外は何もテストする必要はありません。
于 2012-11-15T19:08:47.547 に答える
3

まず、1 は素数ではありません。

次に、100 万番目の素数は 15,485,863 であるため、大規模なデータ処理に備える必要があります。

第三に、おそらくエラトステネスのふるいを使いたいでしょう。ここに簡単なバージョンがあります：

function sieve(n)
    bits := makeArray(0..n, True)
    for p from 2 to n step 1
        if bits[p]
            output p
            for i from p*p to n step p
                bits[i] := False

最初の100万個の素数を計算するために必要な配列のサイズではうまくいかないかもしれません。その場合、エラトステネスのセグメントふるいを実装する必要があります。

私のブログでは、5 つのプログラミング言語で実装された、最適化されたエラトステネスのふるいを提供するエッセイなど、素数に関する多くの作業を行ってきました。

何をするにしても、どのプログラミング言語でも、最初の 100 万個の素数を数秒以内に計算できるはずです。

于 2012-11-16T01:43:35.020 に答える
3

エラトステネスのふるいアルゴリズムを実装して、1 から までの素数を見つけn、必要に応じてその範囲を繰り返し増やしたい場合があります。(つまり、まだ 1,000,000 個の素数が見つかりませんでした)

于 2012-11-15T19:08:59.887 に答える
3

エラトステネスの単純なふるいは、クラッパーのように実行されます。これは、私のボックスで 1 秒もかからずに 1,000,000 番目の素数を計算します。

class PrimeSieve
{
    public List<int> Primes;

    private BitArray Sieve;

    public PrimeSieve(int max)
    {
        Primes = new List<int> { 2, 3 }; // Must include at least 2, 3.
        Sieve = new BitArray(max + 1);
        foreach (var p in Primes)
            for (var i = p * p; i < Sieve.Length; i += p) Sieve[i] = true;
    }

    public int Extend()
    {
        var p = Primes.Last() + 2; // Skip the even numbers.
        while (Sieve[p]) p += 2;
        for (var i = p * p; i < Sieve.Length; i += p) Sieve[i] = true;
        Primes.Add(p);
        return p;
    }
}

編集: Will Ness が正しく指摘しているように、ふるい分けは 2p ではなく p^2 から最適に開始されます (p^2 未満のすべての化合物番号は以前の反復でマークされます)。

于 2012-11-16T01:04:49.563 に答える
1

これはTrial 除算ふるいを実装する Ocaml プログラムです(Will によって正しく指摘されているように、Eratosthenes の逆のようなものです):

(* Creates a function for streaming integers from x onward *)
let stream x =
  let counter = ref (x) in
  fun () ->
    let _ = counter := !counter + 1 in
    !counter;;

(* Filter the given stream of any multiples of x *)
let filter s x = fun () ->
  let rec filter' () = match s () with
    n when n mod x = 0 ->
      filter' ()|
    n ->
      n in
  filter' ();;

(* Get next prime, apply a new filter by that prime to the remainder of the stream *)
let primes count =
  let rec primes' count' s = match count' with
    0 ->
      []|
    _ -> 
      let n = s () in
      n :: primes' (count' - 1) (filter s n) in
  primes' count (stream 1);;

整数のストリームで動作します。新しい素数が発見されるたびに、ストリームにフィルターが追加され、ストリームの残りの部分からその素数の倍数がフィルター処理されます。このプログラムは、オンデマンドで素数を生成するように変更することもできます。

Java で同じアプローチを取るのはかなり簡単なはずです。

お役に立てれば！

于 2012-11-15T20:14:25.220 に答える
-1

5 の後のすべてが 5 で割り切れる 5 で終わるわけではないので、987,985 のように正しい (1,numb)<>"5" の場合はスキップできます。私は Excel で 100 万個の素数をテストし、約 15 秒で列に吐き出すものを作成しましたが、約 1,500 万個になると気が狂いそうになります

于 2015-04-18T18:13:02.580 に答える