java用“埃氏筛法”求2-100以内的素数。先去掉2的倍数,再去掉3 的倍数,在去掉5 的倍数,……依次类推,最后剩下的就是素数。要求使用数组。
时间: 2024-11-06 12:24:18 浏览: 22
sieve-of-Eratosthenes.rar_JAVA埃氏筛法
在Java中,我们可以使用"埃拉托斯特尼筛法"(Sieve of Eratosthenes)来找出2到100之间的所有素数。这个算法基于一个简单的原理:对于每个数i,如果它是素数,那么它就不能被小于它的任何一个已经检查过的合数整除。以下是用数组实现的一个简单示例:
```java
public class PrimeSieve {
public static void main(String[] args) {
int limit = 100; // 定义范围上限
boolean[] primes = new boolean[limit + 1]; // 创建布尔数组,primes[i]表示i是否为素数
// 初始化:将所有数标记为素数
for (int i = 2; i <= limit; i++) {
primes[i] = true;
}
// 根据埃氏筛法剔除非素数
for (int i = 2; i * i <= limit; i++) { // 只需检查到√limit即可
if (primes[i]) { // 如果i是素数
for (int j = i * i; j <= limit; j += i) { // 去掉i的所有倍数
primes[j] = false; // 将它们标记为非素数
}
}
}
// 输出2-100之间的素数
for (int i = 2; i <= limit; i++) {
if (primes[i]) {
System.out.print(i + " ");
}
}
}
}
```
运行这段代码,你会得到2到100之间的所有素数。
阅读全文