D - 2017-like Number

Time limit : 2sec / Memory limit : 256MB

Score : <var>400</var> points

Problem Statement

We say that a odd number <var>N</var> is similar to 2017 when both <var>N</var> and <var>(N+1)⁄2</var> are prime.

You are given <var>Q</var> queries.

In the <var>i</var>-th query, given two odd numbers <var>li</var> and <var>ri</var>, find the number of odd numbers <var>x</var> similar to 2017 such that <var>li≤x≤ri</var>.

Constraints

  • <var>1≤Q≤105</var>
  • <var>1≤li≤ri≤105</var>
  • <var>li</var> and <var>ri</var> are odd.
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

<var>Q</var>
<var>l1</var> <var>r1</var>
<var>:</var>
<var>lQ</var> <var>rQ</var>

Output

Print <var>Q</var> lines. The <var>i</var>-th line <var>(1≤i≤Q)</var> should contain the response to the <var>i</var>-th query.

Sample Input 1

Copy 
1
3 7

Sample Output 1

Copy 
2
  • <var>3</var> is similar to 2017, since both <var>3</var> and <var>(3+1)⁄2=2</var> are prime.
  • <var>5</var> is similar to 2017, since both <var>5</var> and <var>(5+1)⁄2=3</var> are prime.
  • <var>7</var> is not similar to 2017, since <var>(7+1)⁄2=4</var> is not prime, although <var>7</var> is prime.

Thus, the response to the first query should be <var>2</var>.

Sample Input 2

Copy 
4
13 13
7 11
7 11
2017 2017

Sample Output 2

Copy 
1
0
0
1

Note that <var>2017</var> is also similar to 2017.

Sample Input 3

Copy 
6
1 53
13 91
37 55
19 51
73 91
13 49

Sample Output 3

Copy 
4
4
1
1
1
2
【题意】：当N和（N + 1）/ 2都是素数时，奇数N与2017相似。 你有Q个查询。 在第i个查询中，给定两个奇数Li和Ri，找到与2017相似的奇数x的数目，使得li≤x≤ri。
【分析】：筛素数用埃筛，查询用前缀和。
【代码】：
#include<bits/stdc++.h>
using namespace std;
bool f [100001];
int c [100002];
int N,L,R ;
int main ()
{
    for (int i =2; i<=100000; i++)
        if (!f[i])
        for (int j = i+i ;j<=100000; j+=i )
                f[j]= true ;

    for (int i =3; i<=100000; i+=2)
        if (!f[i] && !f[(i+1)/2])
            c[i]++;

    for (int i =3; i <=100000; i ++)
            c[i]+=c[i-1];

    scanf ("%d",&N);
    while (N--)
    {
        scanf ("%d%d" ,&L ,&R );
        printf ("%d\n" , c[R] - c[L-1]);
    }
}
前缀和