蓝桥杯算法提高VIP-找素数-题解（Java代码）

解题思路:

注意事项:

参考代码:

import java.util.Scanner;
public class Main36 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int l = input.nextInt();
        int r = input.nextInt();
        boolean[] b = new boolean[r-l+1];             //使用埃拉托色尼算法变形，直接从l开始标记
        for (int i = 2; i <= r/i; i++) {
            if (i < l || !b[i-l]) {                    //如果i小于l，则b数组不能表示这里的数是否为素数，顾直接执行
                for (int j = i < l/i ? l/i : i ; j <= r/i; j++)            //直接从l/i开始标记，标记为true的为合数
                    if(j*i>=l)                    //如果i是基数，l/i-l=-1会出错，所以在这里判断一下
                        b[j * i - l] = true;        //将j*i-l标记为合数
            }
        }
        int m = 0;
        for (int i = l==0?2:l==1?1:0; i <= r-l; i++)        //如果l为0或1，则0或1不会被标记，会被当做素数计入结果，需要排除
            if (!b[i])                        //被标记的数均为合数，顾没有被标记的为素数
                m++;
        System.out.println(m);
        input.close();
    }
}