Generating Prime Numbers in Java – 在Java中生成素数

最后修改: 2017年 11月 12日

中文/混合/英文(键盘快捷键：t)

1. Introduction

1.介绍

In this tutorial, we’ll show various ways in which we can generate prime numbers using Java.

在本教程中，我们将展示用Java生成素数的各种方法。

If you’re looking to check if a number is prime – here’s a quick guide on how to do that.

如果你想检查一个数字是否是质数–这里有一个快速指南，介绍如何做到这点。

2. Prime Numbers

2.质数

Let’s start with the core definition. A prime number is a natural number greater than one that has no positive divisors other than one and itself.

让我们从核心定义开始。质数是一个大于1的自然数，除了1和它本身之外没有正除数。

For example, 7 is prime because 1 and 7 are its only positive integer factors, whereas 12 is not because it has the divisors 3 and 2 in addition to 1, 4 and 6.

例如，7是质数，因为1和7是它唯一的正整数因子，而12不是，因为它除了1、4和6之外，还有除数3和2。

3. Generating Prime Numbers

3.生成质数

In this section, we’ll see how we can generate prime numbers efficiently that are lower than a given value.

在本节中，我们将看到如何有效地生成低于给定值的素数。

3.1. Java 7 and Before – Brute Force

3.1.Java 7及以前 – 蛮力攻击 

public static List<Integer> primeNumbersBruteForce(int n) {
    List<Integer> primeNumbers = new LinkedList<>();
    for (int i = 2; i <= n; i++) {
        if (isPrimeBruteForce(i)) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}
public static boolean isPrimeBruteForce(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

As you can see, primeNumbersBruteForce is iterating over the numbers from 2 to n and simply calling the isPrimeBruteForce() method to check if a number is prime or not.

正如你所看到的，primeNumbersBruteForce正在遍历2到n的数字，并简单地调用isPrimeBruteForce()方法来检查一个数字是否是质数。

The method checks each numbers divisibility by the numbers in a range from 2 till number-1.

该方法检查每个数字在2至number-1范围内的可除性。

If at any point we encounter a number that is divisible, we return false. At the end when we find that number is not divisible by any of its prior number, we return true indicating its a prime number.

如果在任何时候我们遇到一个数字是可以被除的，我们就返回false。最后当我们发现这个数字不能被它之前的任何一个数字所除，我们就返回true，表明它是一个素数。

3.2. Efficiency and Optimization

3.2.效率和优化

The previous algorithm is not linear and has the time complexity of O(n^2). The algorithm is also not efficient and there’s clearly a room for improvement.

之前的算法不是线性的，其时间复杂度为O(n^2)。该算法的效率也不高，显然还有改进的余地。

Let’s look at the condition in the isPrimeBruteForce() method.

我们来看看isPrimeBruteForce()方法中的条件。

When a number is not a prime, this number can be factored into two factors namely a and b i.e. number = a * b. If both a and b were greater than the square root of n, a*b would be greater than n.

当一个数字不是质数时，这个数字可以被分解成两个因素，即a和b，即number = a * b。 如果a和b都大于n的平方根，a*b将大于n。

So at least one of those factors must be less than or equal the square root of a number and to check if a number is prime, we only need to test for factors lower than or equal to the square root of the number being checked.

因此，这些因子中至少有一个必须小于或等于一个数字的平方根，为了检查一个数字是否是质数，我们只需要测试低于或等于被检查数字的平方根的因子。

Additionally, prime numbers can never be an even number as even numbers are all divisible by 2.

此外，质数永远不可能是偶数，因为偶数都能被2整除。

Keeping in mind above ideas, let’s improve the algorithm:

牢记上述想法，让我们改进算法。

public static List<Integer> primeNumbersBruteForce(int n) {
    List<Integer> primeNumbers = new LinkedList<>();
    if (n >= 2) {
        primeNumbers.add(2);
    }
    for (int i = 3; i <= n; i += 2) {
        if (isPrimeBruteForce(i)) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}
private static boolean isPrimeBruteForce(int number) {
    for (int i = 2; i*i <= number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

3.3. Using Java 8

3.3.使用Java 8

Let’s see how we can rewrite the previous solution using Java 8 idioms:

让我们看看如何使用Java 8的习语重写前面的解决方案。

public static List<Integer> primeNumbersTill(int n) {
    return IntStream.rangeClosed(2, n)
      .filter(x -> isPrime(x)).boxed()
      .collect(Collectors.toList());
}
private static boolean isPrime(int number) {
    return IntStream.rangeClosed(2, (int) (Math.sqrt(number)))
      .allMatch(n -> x % n != 0);
}

3.4. Using Sieve of Eratosthenes

3.4.使用埃拉托什尼的筛子

There’s yet another efficient method which could help us to generate prime numbers efficiently, and it’s called Sieve Of Eratosthenes. Its time efficiency is O(n logn).

还有一种有效的方法可以帮助我们有效地生成素数，它叫做Sieve Of Eratosthenes。它的时间效率是O(n logn)。

Let’s take a look at the steps of this algorithm:

让我们来看看这个算法的步骤。

  1. Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n)
  2. Initially, let p be equal 2, the first prime number
  3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked
  4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3

At the end when the algorithm terminates, all the numbers in the list that are not marked are the prime numbers.

最后，当算法终止时，列表中所有未被标记的数字都是素数。

Here’s what the code looks like:

下面是代码的样子。

public static List<Integer> sieveOfEratosthenes(int n) {
    boolean prime[] = new boolean[n + 1];
    Arrays.fill(prime, true);
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }
    List<Integer> primeNumbers = new LinkedList<>();
    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}

3.5. Working Example of Sieve of Eratosthenes

3.5.埃拉托什尼筛子的工作实例

Let’s see how it works for n=30.

让我们看看对n=30的工作情况。

Primes

Consider the image above, here are the passes made by the algorithm:

考虑到上面的图像，这里是算法所做的传递。

  1. The loop starts with 2, so we leave 2 unmarked and mark all the divisors of 2. It’s marked in image with the red color
  2. The loop moves to 3, so we leave 3 unmarked and mark all the divisors of 3 not already marked. It’s marked in image with the green color
  3. Loop moves to 4, it’s already marked, so we continue
  4. Loop moves to 5, so we leave 5 unmarked and mark all the divisors of 5 not already marked. It’s marked in image with the purple color
  5. We continue above steps until loop is reached equal to square root of n

4. Conclusion

4.结论

In this quick tutorial, we illustrated ways in which we can generate prime numbers until ‘N’ value.

在这个快速教程中，我们说明了在N值之前我们可以生成素数的方法。

The implementation of these examples can be found over on GitHub.

这些示例的实现可以在GitHub上找到over on Git。