1

私の入力はIntegerです。その値までは、すべての素数を見つけて5列に出力する必要があります。次に、整数を「素数分解」して結果を出力する必要があります。

それはうまくいきますが、遅すぎません...

public class Bsp07 {
  public static void main(String[] args) {

     System.out.println("Enter the upper bound for prime number search");
     int n = SavitchIn.readLineInt();
     int[] aZahlen = new int[n - 1];
     for (int el = 0, zahl = 2; el != n - 1; el++, zahl++)
        aZahlen[el] = zahl;

     int p = 2, altesP; // next unmarked number
     boolean aus = false; // when unmarked elements are "aus" (off)

     while (aus == false) {

     // marks Elements; using For loop since for-each loop doesn't work
        for (int i = 0; i < aZahlen.length; i++) {
           if ((aZahlen[i] % p == 0) && (aZahlen[i] != p))
              aZahlen[i] = 0;
        }

        altesP = p; // merkt sich altes p
     // update p, find next unmarked Element
        for (int el : aZahlen) {
           if ((el != 0) && (el > altesP)) {
              p = el;
              break;
           }
        }
     // if p stayed the same unmarked elements are "aus" (off)
        if (altesP == p)
           aus = true;
     }

     int nervVar = 0;
     for (int pr : aZahlen) {
        if(pr==0) 
           continue;
        System.out.print(pr + " ");
        nervVar++;
        if ((nervVar % 5 == 0)) System.out.print("\n");
     }

     /* Factorization */
     System.out.print("\n" + n + " = ");
     for (int i = 0, f = 0; n != 1; i++, f++) {
        while(aZahlen[i]==0) i++;
     /*
      * If the prime divides: divide by it, print the prime,
      * Counter for further continuous decrease with prime number if n = 1,
      * Stop
      */
        if (n % aZahlen[i] == 0) {
           n /= aZahlen[i];
        // So that the first time is not *
           if (f != 0)
              System.out.print(" * " + aZahlen[i]);
           else
              System.out.print(aZahlen[i]);
           i--;
        }
        // So that f remains zero if no division by 2
        else
           f--;
     }
     System.out.println();
  }

}

どこでリソースを節約できますか？ところで、今のところ配列しか使えません...ドイツ語のコメントでごめんなさい。本当に不要な長いループなどが目に入った場合

ありがとう！

4

3 に答える 3

1

まで検索する代わりに、最大までn-1検索し(int) sqrt(n)ます。これで十分な理由を自分で理解してください。;-)

なぜあなたが必要なaltesPのか全くわかりません。2つ増やすことはできませんpか？

殴打してフィルタリングすることはしません。ポジティブリストを作成し、見つけた素数を追加します。

ふるい全体を通過することなく数を除外できる高速プライムネステストを調べてください。

したがって、コードに次の変更を加えてください。

  1. を消去する代わりにaZahlen、のリストを作成しますprimes。sqrtN = (int)sqrt(n)割り当てサイズは問題ないはずなので、foundPrimes知っている素数の数を数えます。

  2. ファズなしでp最大まで繰り返します。<= sqrtN既知の素数のいずれかが除数であるかどうかを確認します。そうでない場合は、新しい素数を見つけました。それを出力し、リストに保存しますfoundPrimes。

于 2012-12-01T13:30:10.423 に答える
-1

はint[]値ごとに32ビットを使用します。これを使用する場合byte[]は値ごとに8ビットを使用し、BitSetを使用する場合は値ごとに1ビットを使用します（32倍小さい）

于 2012-12-01T13:38:07.073 に答える
-1

何をしたいのかわかりません。素数による試行除算で整数を因数分解しようとしていると思います。そのためには、整数よりも小さいすべての素数は必要ありません。整数の平方根よりも小さい素数だけが必要です。したがって、必要なのは、素数を選択するための単純なエラトステネスのふるいです。

function sieve(n)
  bits := makeArray(2..n, True)
  ps := []
  for p from 2 to n
    if bits[p]
      ps.append(p)
      for i from p+p to n step p
        bits[i] = False
  return ps

次に、これらの素数を使用して因数分解を実行できます。

function factors(n)
  ps := primes(sqrt(n))
  fs := []
  p := head(ps)
  while p*p <= n
    if n%p == 0
      fs.append(p)
      n := n / p
    else
      ps := tail(ps)
      p := head(ps)
  fs.append(n)
  return fs

私のブログのエッセイで素数を使ったプログラミングについて説明しています。これには、Javaでのこれら両方のアルゴリズムの実装が含まれています。このエッセイには、上記の方法よりも素数を列挙し、整数を因数分解する他のより効率的な方法も含まれています。

于 2012-12-01T17:55:04.107 に答える