0

我正在编写这个 Java 程序来查找给定范围之间的所有素数。因为我正在处理非常大的数字，所以我的代码似乎不够快并且给了我一个时间错误。这是我的代码，有人知道让它更快吗？谢谢。

import java.util.*;
public class primes2 
{   
    private static Scanner streamReader = new Scanner(System.in);
    public static void main(String[] args)
    {
        int xrange = streamReader.nextInt(); 
        int zrange = streamReader.nextInt();
        for (int checks = xrange; checks <= zrange; checks++)
        {
            boolean[] checkForPrime = Primes(1000000);
            if (checkForPrime[checks])
            {
                System.out.println(checks);
            }
        }
    }
    public static boolean[] Primes(int n)
    {
        boolean[] isPrime = new boolean[n + 1];
        if (n >= 2)
            isPrime[2] = true;
        for (int i = 3; i <= n; i += 2)
            isPrime[i] = true;
        for (int i = 3, end = sqrt(n); i <= end; i += 2)
        {
            if (isPrime[i]) 
            {
                for (int j = i * 3; j <= n; j += i << 1)
                    isPrime[j] = false;
            }
        }
        return isPrime;
    }
    public static int sqrt(int x)
    {
        int y = 0;
        for (int i = 15; i >= 0; i--) 
        {
            y |= 1 << i;
            if (y > 46340 || y * y > x)
                y ^= 1 << i;
        }
        return y;
        }
}
4

3 回答 3

7

只需更改以下内容，您将获得巨大的改进：

    for (int checks = xrange; checks <= zrange; checks++)
    {
        boolean[] checkForPrime = Primes(1000000);

对此：

    boolean[] checkForPrime = Primes(1000000);
    for (int checks = xrange; checks <= zrange; checks++)
    {

您当前的代码会重新生成筛分zrange - xrange + 1时间，但实际上您只需要生成一次。

于 2012-02-24T22:12:09.947 回答
0

明显的问题是您多次计算素数高达 1000000 次（zrange - xrange 次）。另一个是你不需要计算最高 1000000 的素数，你只需要检查最高 zrange 的素数，所以当 zrange < 1000000 时你会浪费时间，而当 zrange > 1000000 时会出现缓冲区溢出。

于 2012-02-24T22:14:49.173 回答
0

您可以从 开始您的内部循环i*i，即for (int j = i * 3; j <= n; j += i << 1)您可以编写代码for (int j = i * i; j <= n; j += i << 1)以实现较小的加速。

此外，您必须确保您zrange的不大于1000000。

如果xrange远大于sqrt(zrange)，您还可以将筛阵列一分为二，用于偏移筛方案。较低的数组将跨越 2 到sqrt(zrange). 上一个将跨越从xrange到zrange。当您筛选下部阵列时，当每个新素数都被它识别时，在您的内部循环内，除了将下部阵列标记到其末端之外，还要筛选上部阵列。您必须计算每个 prime 的起始偏移量i，并使用与2*i下半部分相同的步骤。如果您的范围比几个素数更宽，您将获得速度优势（否则只需按赔率进行尝试划分就足够了）。

要尝试的另一件事是，如果偶数> 2不是素数，为什么要在数组中表示它们并浪费一半的空间？您可以将每个i视为代表一个奇数2*i+1，从而将您的数组压缩成两半。

最后一个简单的技巧是也预先消除 3 的倍数，方法是ON不仅标记odds（即与 互质2）、by { ... i+=2; ...}，而且仅标记与2 和 3、by互质{ ... i+=2; ... i+=4; ... }。另外，在标记OFF素数的倍数时> 3，也要使用{ ... j+=2*i; ... j+=4i; ...}。例如，如果一开始没有标记的倍数，则5*5, 5*7, 5*9, 5*11, ...不需要标记。OFF 5*93ON

于 2012-02-27T11:54:04.700 回答