大白话题解

解题思路:
1、使用正常遍历找出素数，肯定超时

2、交为常用快捷的素数查找方式为：埃氏筛选(可以自行百度)，所以先使用该方法将2~~sqrt(R)中的素数找出，需要建立一个0-sqrt(R)的数组

3、每找出一个素数，都将该数在L~~R区间内的倍数，找出标记为合数(即不是素数),需要建立一个R-L的数组

4、遍历第三步的数组即可获取答案

注意事项:

参考代码:

#include<iostream>

using namespace std;

#include<cmath>

#include<cstring>

const int MAX_SIZE = 1000001; //题目给出的两个变量的差值+1

int base[MAX_SIZE];//埃氏筛选标识素数的数组

int result[MAX_SIZE];//L-R区间标识的数组

int main()

{

int L, R;

cin >> L >> R;

int count = 0;

memset(base, 0, sizeof(base));//初始化为0，即0表示素数，1表示合数

memset(result, 0, sizeof(result));

     for (long i = 2; i <= sqrt(R); i++) {

         if (!base[i]) { // i=2 的时候，会进入 

             for (int j = 2; j*i <= sqrt(R); j++) { // j表示的是 i(素数) 的倍数,即找到一个素数就将其倍数全部标识为合数，即避免进入if语句

                  base[j*i] = 1;

              }

            //因为 i 是素数，所以将 其在 L--R范围内的数，也标记为合数

            //k 表示倍数，所以需要先求得 L 相对于 i 的倍数，倍数需要向上取整 (可以使用c++函数，也可以自己写，比如下面的向上取整方法)

             for (int k = (L / i + (bool)(L % i)); k * i <= R; k++) {

                 if (k != 1) {

                 result[k * i - L] = 1;

                 }

             }

         }

    }

    //遍历数组即可 

    for (int i = 0; i <= R-L; i++) {

         if (result[i] == 0) {

          count++;

        }

    }

    cout << count << endl;

    return 0;

}