0

そこで、素数を生成するアトキンアルゴリズムのふるいを作成しました (プロジェクト オイラーの問題用)。という素数 (int[]) の配列を返しますprimes。問題は、あるインデックスからその配列にアクセスしようとするたびに (mainメソッドでそうする)、例外がスローされることですjava.lang.ArrayIndexOutOfBounds。助けてください（そして、私の論理が妖精と離れていると思われ、これを行う簡単な方法があると思われる場合は、教えてください）！

import java.lang.*;
import java.util.*;

public class SieveOfAtkin {
    public static void main(String[] stuff) {
        int limit = getInt("Limit?");
        int[] p = getPrimes(limit);
        for(int i = 0; i < p.length; i++) {
            System.out.println(p[i]);
        }
    }
    public static int[] getPrimes(int limit) {
        boolean[] isPrime = new boolean[limit + 1];
        double sqrt = Math.sqrt(limit);
        int n = 0;
        for(int i = 0; i < limit + 1; i++) {
            isPrime[i] = false;
        }
        for(int x = 0; x < sqrt; x++) {
            for(int y = 0; y < sqrt; y++) {
                n = 4 * x * x + y * y;
                if(n <= limit && (n % 12 == 1 || n % 12 == 5)) {
                    isPrime[n] = !isPrime[n];
                }
                n = 3 * x * x + y * y;
                if(n <= limit && n % 12 == 7) {
                    isPrime[n] = !isPrime[n];
                }
                n = 3 * x * x - y * y;
                if(n <= limit && n % 12 == 11 && x > y) {
                    isPrime[n] = !isPrime[n];
                }
            }
        }
        for(int i = 5; i < sqrt; i++) {
            if(isPrime[i]) {
                for(int j = i * i; j < limit; j = j + (i * i)) {
                    isPrime[j] = false;
                }
            }
        }
        int count = 0;
        for(int i = 0; i < isPrime.length; i++) {
            if(isPrime[i]) {
                count++;
            }
        }
        int[] primes = new int[count];
        int found = 0;
        if (limit > 2) {
            primes[found++] = 2;
        }
        if (limit > 3) {
            primes[found++] = 3;
        }
        for (int p = 5; p <= limit; p += 2) {
            if (isPrime[p]) {
                primes[found++] = p;
            }
        }
        return primes;
    }
public static int getInt(String prompt) {
    System.out.print(prompt + " ");
    int integer = input.nextInt();
    input.nextLine();
    return integer;
}
}
4

2 に答える 2

2

「無効なインデックスを持つ配列」などはありません。配列にアクセスしていて を取得しているArrayIndexOutOfBounds場合は、負のインデックスを使用しているか、配列が思ったほど大きくありません。コードをデバッグして、配列の実際の長さ ( を使用array.length) を調べ、それを予想した長さと比較します。

編集：さて、コードを取得しました。何が問題なのかがわかります。配列を作成する大きさを計算するとき、値 2 と 3 を数えていませんが、入力するときにそれらを使用していますprimes。したがってprimes、2 つの値は短すぎます。

isPrime[2]これは、とisPrime[3]を に設定することで修正できますtrue。その後、以前の etc のチェックは必要ありません。次limit > 2の全体を反復するだけですprimes。

// After removing the special cases for 2 and 3 before this loop... but setting
// isPrime[2] and isPrime[3] to true
for (int p = 2; p <= limit; p++) {
    if (isPrime[p]) {
        primes[found++] = p;
    }
}
于 2012-06-25T19:19:36.553 に答える
1

問題は、1 を素数としてマークするが、isPrime 配列で 2 と 3 をマークしないため、素数の数をカウントすると、カウントが 1 ずれることです。次に、素数配列の作成を開始するときに、素数 2 と 3 の isPrimes 配列をチェックせずに、それらが正しく計算されていると想定し、それらを素数配列にマークしてから、残りの素数 (現在は1 つ多すぎる）。

ループにデバッグを追加して、素数の数を数え、素数配列に入力すると、簡単に見つけることができます。

于 2012-06-25T20:03:34.370 に答える