java - 查找给定范围内的所有素数

Question

我正在编写这个 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;
        }
}

Answer 1

只需更改此设置，您就会获得巨大的改进:

    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 次，但实际上您只需要生成一次。