NUC1931 Problem D 区间素数【素数筛选】-白红宇

NUC1931 Problem D 区间素数【素数筛选】

阅读量：6956 次

发布时间：2019-06-27

本文共 807 字，大约阅读时间需要 2 分钟。

时间限制: 1000ms 内存限制: 65535KB

问题描述

给定一个闭区间[L,R]，求区间中所包含的素数的个数。

输入描述

有空格分隔开的两个正整数L,R(1≤L≤R≤1000)。

输出描述

闭区间[L,R]中所包含的素数的个数。

样例输入

3 6

样例输出

提示

闭区间[3,6]之间包含两个素数3,5

问题分析：

这个题与《NUC1019 数素数》几乎相同，只是输入格式不同。

用例很多的时候是个坑，所以打表是必须的。

首先用Eratosthenes筛选法求得必要的素数，然后统计个数备用。

程序说明：

数组prime[]开始时存放素数，然后该存放素数的计数值（为了节省空间），prime[i]表示从1开始到i（包括i）的素数个数。

需要注意程序的结束条件，读到EOF时程序结束，判定EOF是个关键。

cin语句判定是否读到EOF的方法见程序。

参考链接：

题记：

无聊凑个数而已！

AC的C++程序如下：

#include 
    
     #include 
     
      using namespace std;const int N = 1000000;int prime[N+1];// Eratosthenes筛选法void sieveofe(int p[], int n){    int i, j;    p[0] = 0;    p[1] = 0;    p[2] = 1;    // 初始化    for(i=3; i
      
       > m >> n))            break;        cout << prime[n] - prime[m-1] << endl;    }    return 0;}