以下是一个使用Java编写的埃拉托斯特尼筛法的示例代码:
import java.util.ArrayList;
import java.util.List;
public class SegmentedSieve {
public static List segmentedSieve(int n) {
int limit = (int) Math.floor(Math.sqrt(n)) + 1;
List primes = sieveOfEratosthenes(limit);
List result = new ArrayList<>();
int low = limit;
int high = 2 * limit;
while (low < n) {
if (high >= n) {
high = n;
}
boolean[] marked = new boolean[limit + 1];
for (int prime : primes) {
int lowLimit = (int) Math.floor(low / prime) * prime;
if (lowLimit < low) {
lowLimit += prime;
}
for (int j = lowLimit; j < high; j += prime) {
marked[j - low] = true;
}
}
for (int i = low; i < high; i++) {
if (!marked[i - low]) {
result.add(i);
}
}
low += limit;
high += limit;
}
return result;
}
public static List sieveOfEratosthenes(int n) {
boolean[] prime = new boolean[n + 1];
for (int i = 0; i <= n; i++) {
prime[i] = true;
}
for (int p = 2; p * p <= n; p++) {
if (prime[p]) {
for (int i = p * p; i <= n; i += p) {
prime[i] = false;
}
}
}
List primes = new ArrayList<>();
for (int p = 2; p <= n; p++) {
if (prime[p]) {
primes.add(p);
}
}
return primes;
}
public static void main(String[] args) {
int n = 100;
List primes = segmentedSieve(n);
System.out.println("Primes less than or equal to " + n + ":");
for (int prime : primes) {
System.out.print(prime + " ");
}
}
}
此示例代码中包含了两个方法:segmentedSieve
和sieveOfEratosthenes
。sieveOfEratosthenes
用于生成小于或等于给定数n
的所有质数,而segmentedSieve
则使用埃拉托斯特尼筛法来生成大于给定数n
的质数。
在main
方法中,我们使用segmentedSieve
方法来找出小于或等于100的所有质数,并将其打印出来。你可以根据需要修改变量n
的值来找出不同范围内的质数。
下一篇:埃拉托斯特尼筛法(使用链表)