认识达内从这里开始

昆明IT培训的小编这一期给大家讲Java质数求解。

质数概念

质数，又称素数，指在一个大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（也可定义为只有1和本身两个因数的数）。最小的素数是2，也是素数中唯一的偶数；其他素数都是奇数。质数有无限多个，所以不存在最大的质数。

目前总结大概有3中计算方式求解，具体如下

1.粗鲁暴力定义求解法

public class Prime {

// find the prime between 1 to 1000;

public static void main(String[] args) {

printPrime(1000);

}

public static void printPrime(int n) {

for (int i = 2; i < n; i++) {

int count = 0;

for (int j = 2; j <= i; j++) {

if (i % j == 0) {

count++;

}

if (j == i && count == 1) {

System.out.print(i + " ");

}

if (count > 1) {

break;

}

}

}

}

}

2.平方根算法(降低循环次数)

public class Prime {

// find the prime between 1 to 1000;

public static void main(String[] args) {

for (int i = 2; i < 1000; i++) {

if (isPrime(i)) {

System.out.print(i + " ");

}

}

}

/**

*求指定数是否为质数

* @param num

* @return

*/

public static boolean isPrime(int num) {

for (int j = 2; j <= Math.sqrt(num); j++) {

if (num % j == 0) {

return false;

}

}

return true;

}

}

3.规律法

最小的素数是2，也是素数中唯一的偶数；其他素数都是奇数。质数有无限多个，所以不存在最大的质数。

public class Prime {

// find the prime between 1 to 1000;

public static void main(String[] args) {

List<Integer> primes = getPrimes(1000);

//输出结果

for (int i = 0; i < primes.size(); i++) {

Integer prime = primes.get(i);

System.out.printf("%8d", prime);

if (i % 10 == 9) {

System.out.println();

}

}

}

/**

*求n以内的所有素数

* @param n 范围

* @return n以内的所有素数

*/

private static List<Integer> getPrimes(int n) {

List<Integer> result = new ArrayList<Integer>();

result.add(2);

for (int i = 3; i <= n; i += 2) {

if (!divisible(i, result)) {

result.add(i);

}

}

return result;

}

/**

*判断n是否能被整除

* @param n      要判断的数字

* @param primes 包含素数的列表

* @return       如果n能被primes中任何一个整除，则返回true。

*/

private static boolean divisible(int n, List<Integer> primes) {

for (Integer prime : primes) {

if (n % prime == 0) {

return true;

}

}

return false;

}

}

第一种和第二种都是很简单的方法：

第三种方法说明了一个质数的特性：在所有质数中，只有2是偶数。如果一个数能够被它之前的质数整除，那么这个数不是质数。