首页 文章

编程以查找非常大的给定整数范围内的所有素数

提问于
浏览 次
5

我在一个编程网站上遇到了以下这个问题：Peter希望为他的密码系统生成一些素数 . 帮助他！您的任务是生成两个给定数字之间的所有素数！

输入

输入以单行中的测试用例数t开始（t <= 10） . 在接下来的t行中的每一行中，存在由空格分隔的两个数m和n（1 <= m <= n <= 1000000000，n-m <= 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之间的素数 .

谢谢，罗希特

java algorithm primes sieve-of-eratosthenes

6 回答

  • 4

    由于m和n之间的距离相对较小，因此您可以在m和n之间的每个数字中强制使用快速素性测试算法 .

    如果允许概率算法，则可以使用Miller-Rabin test . 设M = n-m <= 10 ^ 5且N = n <= 10 ^ 9 . 蛮力算法的复杂性将是O（k M（log N）^ 3），其中k是控制概率保证的常数（对于实际应用，k可以设置为10） .

    对于问题的限制，这种复杂性将在10 ^ 9左右 .

    回复于
  • 0

    你得到了

    1 <= m <= n <= 1000000000，n-m <= 100000

    这些都是非常小的数字 . 要筛选上限为 n 的范围，需要素数为 √n . 在这里你知道 n <= 10^9 ，所以 √n < 31623 ，所以你最需要的是31621的素数 . 有3401.你可以用几微秒的标准筛子生成它们 .

    然后你可以简单地筛选从 m 到 n 的小范围，标记你之前已经过筛过的素数的倍数，当素数超过_509843时停止 . 通过从筛子中消除一些小质数的倍数可以获得一些加速，但逻辑变得更复杂（你需要专门处理小的 m 的筛子） .

    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;
}

    使用 BitSet 或任何其他类型的压缩标志阵列会减少内存使用量，因此可能会因更好的缓存局部性而显着提高速度 .

    回复于
  • 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是偏移量 .

    回复于
  • 1

    您不必强制拥有一个大型数组：您可以保留到目前为止找到的素数列表，并使用多个数组进行测试，其值为= array_slot offset（已测试的值） . 完成从i到j的值后，将j-i添加到偏移量并从J开始新的数组 .

    您可以从数组中删除偶数，这样可以节省一些空间（values = array_slot * 2 - 1） .

    回复于
  • 0

    你 HAVE 将结果存储在数组中？如果一个方法计算给定的整数是否为素数， just 如何为 {left,left+1,...,right} 中的每个数字调用它？

    回复于
  • 0

    使用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;
}
    回复于

相关问题