高效素数计算程序 Java

Question

所以我试图在 java 中制作一个素数计算器，它从 1 到用户给定范围的上限，并打印出所有素数。

解决这个问题的一种方法是简单地使用嵌套 for 循环并测试范围内每个数字是否被小于它的所有数字整除。

不过，我认为只测试质数会更有效，以避免重复因子并加快程序速度。

例如，如果我们的数字是 16，而不是测试它是否可以被 2,3,4,5,...14,15,16 整除，我只能测试 2,3， 5,7,11,13 并在找到一个因子后停止。

所以我尝试创建一个数组来存储到目前为止找到的所有素数，并且只使用这些值来测试下一个数字。

这是我的代码，我不明白为什么它不起作用

    Scanner sc = new Scanner (System.in);
    System.out.print ("Enter the upper limit: ");
    int high = sc.nextInt();

    boolean isPrime = true;
    int[] primearray = new int[0];

    for (int num = 1; num <= high; num++)
    {
        for (int x: primearray)
        {
            if (num%x==0)
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime == true) {
            int size = primearray.length;
            primearray = new int[size+1];
            primearray [size] = num;

            System.out.println (num);
        }
    }

Answer 1

首先，1 不是素数。通过从 1 开始你的外循环，你的素数数组以 1 结束，然后其他所有内容都将被测试为不是素数。在 int num = 2.

开始你的外循环

其次，当您扩展 primearray 时，您并没有复制现有的已知素数。您可以使用

primearray = Arrays.copyOf(primearray, size+1);

这将创建一个包含所有旧内容的新数组，并 space 多一个值。

最后，您可能想查看 Sieve of Eratosthenes. A careful implementation of that algorithm will be more efficient than your current algorithm, which requires an expensive array reallocation every time you find a prime. You can use a BitSet 以跟踪筛子需要的标志。

Answer 2

正如您所说，关键的简化是仅在找到下一个素数时才测试素数。例如：

public class PrimeGenerator {
    private long current = 1;
    private final List<Long> primes = new ArrayList<>();

    public long next() {
        do {
            current++;
        } while (primes.stream().anyMatch(n -> current % n == 0));
        primes.add(current);
        return current;
    }

    public LongStream stream() {
        return LongStream.generate(this::next);
    }
}

这会记录每个生成的素数。

您可以使用

将所有素数生成为特定值

generator.stream().takeWhile(p -> p < value)...

Answer 3

你逻辑有问题

boolean isPrime = true;

这个变量应该在for循环中声明，想象一下，如果你发现4不是素数那么isPrime = false，那么你检查5但是没有设置 isPrime = true.

的任何代码块

而这个区块：

if (isPrime == true) {
    int size = primearray.length;
    primearray = new int[size+1];
    primearray [size] = num;

    System.out.println (num);
}

您创建了新的素数数组，primearray，大小增加了 1，因此 primearray 不包含任何旧素数，这会在检查素数时出错。所以你需要将旧素数复制到新数组中。

并且因为素数以 2 开头，所以您的代码应该是：

Scanner sc = new Scanner(System.in);
System.out.print("Enter the upper limit: ");
int high = sc.nextInt();

int[] primeArray = new int[0];
for (int num = 2; num <= high; num++)
{
    boolean isPrime = true;
    for (int x : primeArray)
    {
        if (num % x == 0)
        {
            isPrime = false;
            break;
        }
    }

    if (isPrime == true)
    {
        primeArray = Arrays.copyOf(primeArray, primeArray.length + 1);
        primeArray[primeArray.length - 1] = num;
        System.out.println(num);
    }
}

Answer 4

之前的回答已经解释了你的代码有什么问题。

我只想分享另一种更有效的方法。示例实现如下所示。基本上，一旦我们知道 x 是素数，我们也知道 i*x 不是素数。可以进一步阅读和可视化 here

public int countPrimes(int n) {
            if (n == 0 || n == 1) return 0;

    int count = 0;
    boolean[] check = new boolean[n+1];

    for (int i = 2; i < n; i++) {
        if (check[i]) continue;

        for (int j = 1; j <= n / i; j++) {
            check[j * i] = true;
        }

        count++;
    }

    return count;
}

Answer 5

您应该使用埃拉托色尼筛法来查找素数，而不是测试每个数的可整除性；该方法比筛分慢得多。这是从 my blog:

筛选的实现

public static LinkedList sieve(int n)
{
    BitSet b = new BitSet(n);
    LinkedList ps = new LinkedList();

    b.set(0,n);

    for (int p=2; p<n; p++)
    {
        if (b.get(p))
        {
            ps.add(p);
            for (int i=p+p; i<n; i+=p)
            {
                b.clear(i);
            }
        }
    }

    return ps;
}

高效素数计算程序 Java

Efficient Prime Number Computing Program Java

java

primes

bluej