我正在编写此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;
}
}
最佳答案
只需更改以下内容,即可获得巨大的改进:
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
次,但实际上您只需要生成一次即可。