素数筛选算法：从基础试除法到埃氏筛优化

1. 项目概述

这道编程题目来自信息学奥赛经典教材《信息奥赛一本通》的编程启蒙部分，编号3346，题目名为"【例60.3】 找素数"。这是一道典型的素数筛选练习题，旨在帮助初学者掌握基本的算法思维和编程实现能力。

素数判断是编程竞赛中最基础也是最重要的算法之一。这道题目要求我们找出给定区间内的所有素数，看似简单，但其中蕴含着许多值得深入探讨的算法优化技巧。在实际编程竞赛中，高效的素数筛选算法往往能决定程序能否在规定时间内完成大规模数据的处理。

2. 核心需求解析

2.1 题目要求详解

题目通常会给出一个区间[a,b]，要求输出这个区间内所有的素数。例如：

• 输入：10 20
• 输出：11 13 17 19

从表面看，这只是一个简单的遍历判断问题，但实际上需要考虑以下几个关键点：

1. 边界条件处理：需要正确处理a和b的大小关系，以及负数、0、1等特殊情况
2. 算法效率：当区间范围很大时(如1到10^6)，简单的逐个判断方法会非常耗时
3. 输出格式：需要按照要求的格式输出素数，通常是用空格分隔

2.2 素数判断的基本方法

最直观的素数判断方法是试除法：对于一个数n，从2到n-1逐个试除，如果都不能整除，则n是素数。这种方法虽然简单，但效率极低，时间复杂度为O(n)。

改进版的试除法可以只检查2到√n之间的数，因为如果n有大于√n的因数，那么它必然有一个小于√n的对应因数。这样时间复杂度降为O(√n)。

cpp复制bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

3. 高效算法实现

3.1 埃拉托斯特尼筛法

对于需要找出一个区间内所有素数的情况，更高效的算法是埃拉托斯特尼筛法（埃氏筛）。其基本思想是：

1. 初始化一个布尔数组isPrime[]，标记所有数为素数(true)
2. 从2开始，将每个素数的倍数都标记为非素数(false)
3. 最后仍标记为true的数就是素数

cpp复制void s