欧拉筛法

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        if (x > y) {
            int temp = x;
            x = y;
            y = temp;
        }

        boolean[] isPrime = new boolean[y + 1];
        isPrime[0] = isPrime[1] = true;
        int[] primes = new int[y + 1]; // 存储素数的数组
        int count = 0; // 素数的数量

        for (int i = 2; i <= y; i++) {
            // 如果当前i是素数，则将其加入到primes数组中
            if (!isPrime[i]) {
                primes[count++] = i;
            }
            // 用当前已经筛选出的素数去筛i的倍数
            for (int j = 0; j < count && i * primes[j] <= y; j++) {
                isPrime[i * primes[j]] = true; // 标记i的倍数为非素数
                if (i % primes[j] == 0) break; // 关键，保证每个合数只被其最小素因子筛选一次
            }
        }

        // 计算区间[x, y]内素数的数量
        int numPrimesInRange = 0;
        for (int i = x; i <= y; i++) {
            if (!isPrime[i]) {
                numPrimesInRange++;
            }
        }

        System.out.println(numPrimesInRange);
    }
}

欧拉筛法和埃拉托斯特尼筛法（简称埃氏筛）都是用来找出一定范围内所有素数的算法。尽管它们的目标相同，但在执行过程和效率上有所区别。理解这些差异有助于选择适合特定问题的最优算法。

埃拉托斯特尼筛法（埃氏筛）

埃氏筛的基本思想是从小到大遍历每个数，对于每个数，如果它是素数，则将其所有的倍数标记为非素数。这个过程中，每个合数会被其最小的素因子所筛选。

特点

• 简单直观：算法易于理解和实现。
• 重复筛选：一个合数可能被它的多个素因子重复标记为非素数。例如，6会被2和3各标记一次。
• 效率问题：对于大范围的筛选，重复标记合数的操作会导致效率低下。

欧拉筛法（线性筛）

欧拉筛法（也称线性筛）改进了埃氏筛的效率问题。它的核心优化是确保每个合数只被其最小的素因子筛选一次，这样就避免了重复筛选的开销。

特点

• 高效：每个数只被它的最小素因子筛选，保证了每个数只被筛选一次，从而达到线性时间复杂度。
• 复杂度：尽管理论上更高效，但算法实现相较于埃氏筛稍微复杂一些。
• 避免重复：通过巧妙的策略，避免了合数的重复筛选。具体来说，对于每个素数p和当前遍历到的数i，如果i % p == 0，则停止当前循环。这保证了每个合数只被它的最小素因子p筛选，因为一旦i % p == 0，后续的i * p'（p' > p）就不再是p’的最小筛选素因子了。

区别总结

• 效率：欧拉筛法在理论上更高效，因为它避免了重复筛选合数的操作，保证了线性的时间复杂度。
• 实现复杂度：埃氏筛更简单易懂，适合教学和理解素数筛选的基本概念。欧拉筛法虽然更高效，但实现稍微复杂，需要理解避免重复筛选的策略。
• 适用场景：对于小范围内的素数筛选，两种方法都很有效。但是，在处理大范围数据时，欧拉筛法由于其高效性，通常是更好的选择。

选择哪种筛法取决于具体的应用场景和对效率的需求。对于教学和理解基础概念，埃氏筛是一个很好的起点。对于需要高效处理大量数据的场景，欧拉筛法更为适用。