Java求1到100的素数
以下是几种在Java中找出1到100之间所有素数的实现方法：
简单试除法
public class PrimeNumbers {
public static void main(String[] args) {
System.out.println("1到100之间的素数有：");
for (int i = 2; i <= 100; i++) {
if (isPrime(i)) {
System.out.print(i + " ");
}
}
}
// 判断一个数是否为素数
public static boolean isPrime(int num) {
if (num <= 1) {
return false;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
}
埃拉托斯特尼筛法（更高效）
import java.util.Arrays;
public class SieveOfEratosthenes {
public static void main(String[] args) {
int n = 100;
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
// 0和1不是素数
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
// 将i的倍数标记为非素数
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
// 输出素数
System.out.println("1到100之间的素数有：");
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
System.out.print(i + " ");
}
}
}
}
优化后的试除法
public class OptimizedPrimeCheck {
public static void main(String[] args) {
System.out.println("1到100之间的素数有：");
for (int i = 2; i <= 100; i++) {
if (isPrimeOptimized(i)) {
System.out.print(i + " ");
}
}
}
// 优化后的素数判断
public static boolean isPrimeOptimized(int num) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 == 0 || num % 3 == 0) return false;
// 检查6k±1形式的数
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
}
输出结果
所有方法都会输出相同的结果：
1到100之间的素数有：
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 方法比较
- 简单试除法：最容易理解，但对于大数效率较低
- 埃拉托斯特尼筛法：对于找出一定范围内的所有素数非常高效
- 优化后的试除法：在判断单个数是否为素数时效率较高，特别是对于大数
对于1到100这样的小范围，任何方法都可以满足需求，如果需要处理更大的范围,建议使用筛法或优化后的试除法。
