高效寻找第n个质数：内存优化策略
寻找第n个质数的算法通常涉及大量数字的质数判定，直接使用嵌套循环的朴素方法会导致内存占用过高。本文介绍一种基于埃拉托斯特尼筛法的优化方法，有效降低内存消耗。
埃拉托斯特尼筛法是一种高效的质数筛选算法。它首先创建一个布尔数组，初始时所有元素都标记为质数（true）。然后，从2开始，依次遍历每个数字：如果一个数字是质数，则将其所有倍数标记为非质数（false）。最终，数组中标记为true的数字即为质数。
改进后的代码如下：
import java.util.Scanner;
import java.util.Arrays;
public class PrimeFinderOptimized {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.close();
// 使用boolean数组，true表示质数，false表示非质数
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false; // 0和1不是质数
// 埃拉托斯特尼筛法
for (int p = 2; p * p <= n; p++) {
if (isPrime[p]) {
for (int i = p * p; i <= n; i += p) {
isPrime[i] = false;
}
}
}
// 统计质数个数
int count = 0;
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
count++;
}
if (count == n) {
System.out.println(i); // 输出第n个质数
break;
}
}
}
}
通过使用埃拉托斯特尼筛法，该代码显著减少了内存占用，能够在内存限制条件下高效地找到第n个质数。 代码优化主要体现在避免了重复的质数判定，只进行一次筛选，从而提升效率并降低内存需求。
