5

プログラミング Web サイトで、次の質問に出くわしました。Peter は、彼の暗号システム用にいくつかの素数を生成したいと考えています。彼を助けて！あなたの仕事は、与えられた 2 つの数の間のすべての素数を生成することです!

入力

入力は、1 行のテスト ケースの数 t で始まります (t<=10)。次の t 行のそれぞれには、スペースで区切られた 2 つの数値 m と n (1 <= m <= n <= 1000000000、nm<=100000) があります。

私は次の解決策を思いつきました：

import java.util.*;

public class PRIME1 {
    static int numCases;
    static int left, right;
    static boolean[] initSieve = new boolean[32000];
    static boolean[] answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        numCases = sc.nextInt();
        initSieve[0] = true;
        initSieve[1] = true;
        Sieve();
        for (int j = 0; j < numCases; j++) {
            String line = sc.next();
            String line2 = sc.next();
            left = Integer.parseInt(line);
            right = Integer.parseInt(line2);
            answer = new boolean[right - left + 1];
            getAnswer();
            for (int i = 0; i < answer.length; i++) {
                if (!answer[i]) {
                    int ans = i + left;
                    System.out.println(ans);
                }
            }
            System.out.println();
        }
    }

    public static void Sieve() {

        for (int i = 2; i < 32000; i++) {
            if (!initSieve[i]) {
                for (int j = 2 * i; j < 32000; j += i) {
                    initSieve[j] = true;
                }
            }
            if (i * i > 32000)
                break;
        }
    }

    public static void getAnswer() {
        for (int i = 2; i < 32000 && i <= right; i++) {
            if (!initSieve[i]) {
                int num = i;
                if (num * 2 >= left) {
                    num *= 2;
                } else {
                    num = (num * (left / num));
                    if (num < left)
                        num += i;
                }
                for (int j = num; j >= left && j <= right; j += i) {
                    answer[j - left] = true;
                }
            }
        }
    }
}

いくつかの提案を読んだ後、ソリューションを編集しました。私はまだ時間制限を超えた種類のエラーを取得しています。これをさらに最適化する方法として、他に何か提案はありますか? 32000 までのすべての素数を計算し、これらを使用して n から m までの素数を見つけます。

ありがとう、ロヒット

4

6 に答える 6

4

あなたは与えられています

1 <= m <= n <= 1000000000、nm<=100000

これらは非常に小さな数字です。の上限で範囲をふるいnにかけるには、素数が に必要です√n。n <= 10^9ですから、最悪でも 31621 までの素数が必要です。3401√n < 31623あります。標準ふるいを使用して、数マイクロ秒でそれらを生成できます。

次に、以前にふるい分けた素数の倍数をマークし、素数が を超えたときに停止することで、からmまでの小さな範囲を簡単にふるい分けることができます。ふるいからいくつかの小さな素数の倍数を削除することで、ある程度の速度向上が得られますが、ロジックはより複雑になります (小さな素数を持つふるいを特別に扱う必要があります)。n√nm

public int[] chunk(int m, int n) {
    if (n < 2) return null;
    if (m < 2) m = 2;
    if (n < m) throw new IllegalArgumentException("Borked");
    int root = (int)Math.sqrt((double)n);
    boolean[] sieve = new boolean[n-m+1];
    // primes is the global array of primes to 31621 populated earlier
    // primeCount is the number of primes stored in primes, i.e. 3401
    // We ignore even numbers, but keep them in the sieve to avoid index arithmetic.
    // It would be very simple to omit them, though.
    for(int i = 1, p = primes[1]; i < primeCount; ++i) {
        if ((p = primes[i]) > root) break;
        int mult;
        if (p*p < m) {
            mult = (m-1)/p+1;
            if (mult % 2 == 0) ++mult;
            mult = p*mult;
        } else {
            mult = p*p;
        }
        for(; mult <= n; mult += 2*p) {
            sieve[mult-m] = true;
        }
    }
    int count = m == 2 ? 1 : 0;
    for(int i = 1 - m%2; i < n-m; i += 2) {
        if (!sieve[i]) ++count;
    }
    int sievedPrimes[] = new int[count];
    int pi = 0;
    if (m == 2) {
        sievedPrimes[0] = 2;
        pi = 1;
    }
    for(int i = 1 - m%2; i < n-m; i += 2) {
        if (!sieve[i]) {
            sievedPrimes[pi++] = m+i;
        }
    }
    return sievedPrimes;
}

aBitSetまたはその他のタイプのパックされたフラグ配列を使用すると、メモリ使用量が削減されるため、キャッシュの局所性が向上するため、速度が大幅に向上する可能性があります。

于 2012-05-22T14:48:00.563 に答える
1

ブール値の配列の代わりに BitSet を使用します。

public static BitSet primes (final int MAX)
{
     BitSet primes = new BitSet (MAX);
     // make only odd numbers candidates...
     for (int i = 3; i < MAX; i+=2)
     {
        primes.set(i);
     }
     // ... except no. 2
     primes.set (2, true);
     for (int i = 3; i < MAX; i+=2)
     {
        /*
            If a number z is already  eliminated (like 9),
             because it is itself a multiple of a prime 
            (example: 3), then all multiples of z (9) are
            already eliminated.
        */
        if (primes.get (i))
        {
            int j = 3 * i;
            while (j < MAX)
            {
                if (primes.get (j))
                    primes.set (j, false);
                j += (2 * i);
            }
        }
    }
    return primes;
}
于 2012-05-22T14:09:09.113 に答える
0

isNotPrime配列にアクセスするときは、いつでもオフセットを使用できます。

与えられたm、n：

boolean[] isNotPrime = new boolean[n-m+1];

// to now if number x is primer or not
boolean xIsPrime = isNotPrime[x-m];

ここで、mはオフセットです。

于 2012-05-22T14:22:09.600 に答える
0

結果を配列に格納する必要がありますか? 与えられた整数が素数であるかどうかを計算し、 の各数値に対して呼び出すだけ{left,left+1,...,right}のメソッドはどうですか?

于 2012-05-22T14:19:50.760 に答える
0

m と n の間の距離は比較的小さいため、m と n の間のすべての数で力ずくで高速な素数性テスト アルゴリズムを使用できます。

確率的アルゴリズムを許可する場合は、Miller-Rabin testを使用できます。M = nm <= 10^5 および N = n <= 10^9 とします。ブルート フォース アルゴリズムの複雑さは O(k M (log N)^3) になります。ここで、k は確率論的保証を制御する定数です (実際のアプリケーションでは、k を 10 に設定できます)。

問題の限界として、この複雑さは約 10^9 になります。

于 2012-05-22T18:48:04.130 に答える
0

1 つの大きな配列を持つ必要はありません。これまでに見つかった素数のリストを保持し、値 = array_slot + offset(既にテストされた値) を持つ複数の配列を使用してテストできます。i から j までの値が完成したら、ji をオフセットに追加し、J から始まる新しい配列を開始します。

配列から偶数を削除すると、スペースを節約できます (値 = array_slot * 2 - 1)。

于 2012-05-22T14:36:25.287 に答える