## 1.介绍。

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

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

## 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.

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.

## 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及以前 – 蛮力攻击。

``````public static List<Integer> primeNumbersBruteForce(int n) {
for (int i = 2; i <= n; i++) {
if (isPrimeBruteForce(i)) {
}
}
}
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.

The method checks each numbers divisibility by the numbers in a range from 2 till 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.

### 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.

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

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.

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.

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

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

### 3.3.使用Java 8</strong

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

``````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.使用埃拉托什尼的筛子。

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).

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;
}
}
}
for (int i = 2; i <= n; i++) {
if (prime[i]) {
}
}
}
``````

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

Let’s see how it works for n=30. 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.结论。

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

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