什么是质数？

质数是大于1的自然数，只能除以1及其本身。

例如，5是质数，因为它只能除以1和5。

同样，6不是质数，因为它可以除以1、2、3和6。

查找介于1和N之间的质数的算法

有很多算法可以找到给定范围内的素数。
" Eratosthenes筛"是一种流行的且简单的算法，可以找到指定范围内的质数。

查找介于1和N之间的质数的算法具有以下步骤。

• 创建一个从2到N的连续数字列表，即(2,3,4…N)。

• 从第一个和最小的素数2开始。
  假设变量p = 2。

• 找出p的倍数，即2p，3p，4p直到N，并在列表中将其标记为非素数。
  请注意，数字p本身不应标记。

• 在列表中找到未标记的下一个号码，并按照前面的步骤操作。

• 当列表中的数字用完时，算法终止。
  未标记的数字列表是1到N之间的质数。

下面的GIF给出了算法的直观表示(来源：Wikipedia)。

Eratosthenes筛选算法

查找1到N之间的质数的Java实现

package com.theitroad.examples;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PrimeNumbers {

	public static void main(String[] args) {
		System.out.println(findPrimeNumbers(100));
	}

	//generating the list of prime numbers from 2 to the given number
	//using the Sieve of Eratosthenes algorithm
	private static List<Integer> findPrimeNumbers(int n) {
		//initialize the array with "true", index denotes the numbers from 0 to n.
		boolean[] primes = new boolean[n + 1];
		Arrays.fill(primes, true);

		//loop from 2 to x until x*x becomes greater than n
		for (int i = 2; i * i < n; i++) {
			//process if the number is not already marked
			if (primes[i]) {
				//find the multiples and mark them as false
				for (int j = i * i; j <= n; j += i)
					primes[j] = false;
			}
		}

		//populate the list of prime numbers from the array and return it
		List<Integer> primeNumbers = new ArrayList<>();
		for (int i = 2; i <= n; i++) {
			if (primes[i])
				primeNumbers.add(i);
		}
		return primeNumbers;
	}

}

输出：[2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83， 89，97]

检查数字是否为素数的算法？

检查数字是否为质数的最简单方法是使用试验除法。

对于给定的数字N，请检查是否有一个2到√N(平方根)之间的质数M对其进行平均除法，即余数为0。

如果有一个数M均匀地除以N，则N不是质数。
否则，N是质数。

Java实现检查素数

这是检查数字是否为质数的实现。
我们将使用较早定义的方法来找出2到√N之间的质数。

package com.theitroad.examples;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PrimeNumbers {

	public static void main(String[] args) {

		int number = 123456789;

		boolean isPrime = checkPrime(number);

		System.out.printf("%d is Prime: %b.\n", number, isPrime);

		System.out.printf("%d is Prime: %b.\n", 3511, checkPrime(3511));

		System.out.printf("%d is Prime: %b.\n", 123, checkPrime(123));

	}

	//a number is not prime if there is a prime number between 2 to the square root of
	//num that evenly divides it
	private static boolean checkPrime(int num) {
		//get the prime numbers from 2 to square root of num.
		List<Integer> primes = findPrimeNumbers(Double.valueOf(Math.sqrt(num)).intValue());
		System.out.println(primes);

		for (int i : primes) {
			if (num % i == 0) {
				System.out.printf("%d is divided by %d.\n", num, i);
				return false;
			}
		}
		return true;
	}
}