一、什么是素数
素数（Prime Number），又称质数，是指在大于1的自然数中，只能被1和它本身整除的数。
例如：
2、3、5、7、11、13、17、19...
都是素数。
而下面这些数不是素数：
4 = 2 × 2
6 = 2 × 3
8 = 2 × 4
9 = 3 × 3
因为它们除了1和自身外，还能被其他整数整除。
二、素数的特点
-
1不是素数
因为素数必须恰好有两个正因数：
1 和自身
而数字1只有一个因数：
1
因此：
1 不是素数 -
2是唯一的偶数素数
除了2以外：
4、6、8、10...
都能被2整除，因此不是素数。
所以：
2 是唯一的偶数素数 -
所有素数只能被1和自身整除
例如：
13
它只能被：
1 和 13
整除。
三、判断素数的基本思路
判断一个数字n是否为素数：
方法一：逐个试除
检查：
2 ~ n-1
之间是否存在能整除n的数。
例如判断13：
13 ÷ 2
13 ÷ 3
13 ÷ 4
...
13 ÷ 12
如果都不能整除，则13是素数。
Java实现
public class PrimeTest {
public static void main(String[] args) {int n = 13;
boolean isPrime = true;for(int i = 2; i < n; i++) {
if(n % i == 0) {
isPrime = false;
break;
}
}if(isPrime) {
System.out.println(n + "是素数");
} else {
System.out.println(n + "不是素数");
}
}
}
运行结果：
13是素数
四、优化算法
实际上不需要检查到：
n - 1
只需要检查到：
√n
即可。
原理
假设：
n = a × b
如果：
a > √n
并且
b > √n
那么：
a × b > n
矛盾。
因此：
至少有一个因子小于等于√n
只需检查到平方根即可。
优化后的代码
public class PrimeTest {
public static void main(String[] args) {int n = 97;
boolean isPrime = true;for(int i = 2; i <= Math.sqrt(n); i++) {
if(n % i == 0) {
isPrime = false;
break;
}
}if(isPrime) {
System.out.println(n + "是素数");
} else {
System.out.println(n + "不是素数");
}
}
}
五、输出100以内所有素数
实现思路
外层循环：
2~100
依次判断。
内层循环：
检查是否存在因子
Java代码
public class PrimeNumbers {public static void main(String[] args) {
for(int num = 2; num <= 100; num++) {
boolean isPrime = true;
for(int i = 2; i <= Math.sqrt(num); i++) {
if(num % i == 0) {
isPrime = false;
break;
}
}if(isPrime) {
System.out.print(num + " ");
}
}
}
}
运行结果：
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
六、埃拉托斯特尼筛法
当需要寻找大量素数时，可以使用更高效的算法：
筛法思想
以100以内素数为例：
首先写出：
2~100
然后：
保留2
删除2的倍数
保留3
删除3的倍数
保留5
删除5的倍数
不断重复。
最后剩余的数字就是素数。
Java实现
public class SievePrime {public static void main(String[] args) {
int n = 100;
boolean[] isPrime = new boolean[n + 1];
for(int i = 2; i <= n; i++) {
isPrime[i] = true;
}for(int i = 2; i * i <= n; i++) {
if(isPrime[i]) {
for(int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}for(int i = 2; i <= n; i++) {
if(isPrime[i]) {
System.out.print(i + " ");
}
}
}
}
七、学习总结
素数是数学和计算机科学中的重要概念。通过学习素数的定义、判断方法以及埃拉托斯特尼筛法，我掌握了如何利用Java程序判断一个数是否为素数，以及如何高效地求解一定范围内的所有素数。
在编程实践中，普通试除法适用于小规模数据，而筛法适用于大规模素数求解。通过本次学习，我进一步提高了Java循环结构、条件判断以及算法优化方面的能力，也加深了对数论基础知识的理解。