如何高效生成第n个质数（不依赖内置isPrime函数）

本文提供一种基于已知质数数组动态筛除的算法，用于准确计算第n个质数，重点修复了循环计数逻辑错误与数组索引越界问题，并给出可运行的ja va实现。

在不能直接调标准库 isPrime() 的情况下，要算出第 n 个质数，最朴素的思路就是：维护一个已发现的质数列表，然后用列表里的每个质数去试除候选数——只要有一个能整除，候选数就不是质数。这个思路本身没错，但实际写代码时，两个关键细节一不留神就会踩坑：变量作用域放错位置，以及计数更新的时机不对。结果就是，输入大于 2 时程序要么死循环，要么数组越界，啥也输出不出来。

问题出在哪儿呢？原始代码里，num_primes 这个变量被定义在 do-while 循环体内部，每次迭代都重新初始化为 0。这意味着 primes[num_primes] = prime 这行代码永远只会往 primes[1] 里写值，第二个质数（也就是 3）刚存进去就被覆盖了。而 primes[2] 及之后的位置永远保持默认值 0，导致循环条件 primes[num - 1] == 0 永远为真，程序就在那里空转。

更糟的是，num_primes++ 被写在了所有场景下都执行的位置，而不是等确认找到新质数之后才递增。这进一步把数组索引搅得一团糟，存储逻辑彻底失效。

下面这个版本修掉了上述两个坑，直接拷贝就能跑：

import ja va.util.Scanner;

class PrimeNumberFinder {
    static boolean is_prime(int number, int[] prime_numbers) {
        for (int prime : prime_numbers) {
            if (prime == 0) break; // 遇到未初始化项，终止检查
            if (number % prime == 0) {
                return false;
            }
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the nth prime number you want: ");
        int n = scanner.nextInt();
        if (n <= 0) {
            System.out.println("n must be a positive integer.");
            return;
        }
        int[] primes = new int[n];
        primes[0] = 2; // 第一个质数是2
        int candidate = 2; // 当前待检测数（从2开始递增）
        int count = 0;      // 已找到质数个数，初始为1（因primes[0]已设为2）

        // 当尚未填满primes数组时继续搜索
        while (count < n - 1) {
            candidate++;
            if (PrimeNumberFinder.is_prime(candidate, primes)) {
                primes[++count] = candidate; // 找到新质数，先递增再赋值
            }
        }

        System.out.printf("The %d%s prime number is %d%n", 
            n, 
            n == 1 ? "st" : n == 2 ? "nd" : n == 3 ? "rd" : "th",
            primes[n - 1]);
        scanner.close();
    }
}

关键改进说明：

• ✅ count 现在声明在循环外面，准确跟踪已存入的质数数量。初始值为 0 时，primes[0] 已经手动设为 2，所以后续从 candidate=3 开始检测；
• ✅ 用 while (count < n - 1) 替换原来的 do-while + 零值判断，终止条件一目了然，再也不会因为数组残留值判断出错；
• ✅ is_prime() 里加了一行 if (prime == 0) break;，防止遍历到数组尾部未初始化的位置，逻辑更健壮；
• ✅ 输出格式化自动带上序数后缀（1st, 2nd, 3rd…），读起来更顺眼；
• ✅ 入口处做了输入合法性校验，n 为负或零直接报错退出，不会让程序意外异常。

注意事项：

• 这个算法的时间复杂度大体是 O(n² log n) 级别，实测下来 n ≤ 10000 都还能接受。如果目标 n 再大，建议升级为埃拉托斯特尼筛法或者分段筛；
• 数组 primes 长度固定为 n，内存占用可控，但无法动态扩容——一次性申请够用就行；
• candidate 从 2 开始逐一递增，虽然会检查偶数（比如 4、6…），但 is_prime 里第一步就会被 2 整除快速排除，实际开销并不大。

修复的核心就两件事：把变量的生命周期管好，把计数更新的条件找准。改完之后，这段代码就变成了一个简洁、正确、可扩展的第 n 个质数生成器。对理解质数判定与增量构造思想来说，它是个相当不错的实践范例。