乐趣区

AtCoder-ContextABC-084-D-2017like-Number

jiezi

本文章为原创文章，未经过允许不得转载
运行要求
运行时间限制: 2sec
内存限制: 1024MB
未经允许，不得许转载
原题链接

题目
如果有一个奇数 N，N 和 (N+1//2) 都是素数的话，N 为 2017 的相似数
现在给定 Q 次查询
第 i(1<=i<=Q)次查询, 第 i 次查询给定奇数 li，ri，求 li<=x<=ri 范围内，2017 相似数的 x 的个数

输入前提条件

  • 1<=Q<=100000
  • 1<=li<=ri<=100000
  • li,ri 为奇数
  • 所有的输入都为整数

输入
输入按照以下形式标准输入

Q
l1 r1
l2 r1
.
.
.
lQ rQ

输出
第 i 行输出，第 i 次查询的结果

例 1
输入

1
3 7

输出

2

3 和 ((3+1)/2) 都为素数，所以 3 为 2017 的相似数
5 和((5+1)/2) 都为素数，所以 5 为 2017 的相似数
7 虽然是素数，但是 5((7+1)/2) 不是素数，所以 7 不是 2017 的相似数
以上所述，查询 1 的结果为 2

例 2
输入

4
13 13
7 11
7 11
2017 2017

输出

1
0
0
1

注意 2017 也是 2017 的相似数

例 2
输入

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

输出

4
4
1
1
1
2

读懂题目
给定一个区间，在这个区间的所有素数当中，挑选出折半以后仍然是素数的数字

解题思路
首先我们要看到 li，ri 的最大值是 100000，最小值是 1
li，ri 决定了区间的左边界和右边界
所以区间的最大跨度是 1 到 100000

首先我们要找到这个区间里面的所有的素数
因为是代码竞技所以不能使用第三方的扩展包
我们手写素数生成器
具体的方法用到素数筛选法
英文叫 sieve of Eratosthenes


我们取一串区间，记住最少要从 2 开始。我们找出这串数字的最小的元素，这里为 2
先找出 2 的倍数，然后去掉它们


在从剩下的里面找第 1 个没有被遍历的元素，这里是 3
找出 3 的倍数，然后去掉它们


依此类推，找出 5 的倍数，去掉他们


有的时候，最小元素的倍数不存在了，那么什么都不用做


以这种方式可以找到所有的素数

但是有一点要注意的是，遍历结束的标志。
区间从 2 到某个地方的方
start 可以从区间的开头遍历到区间的结尾，但是如果区间很大的话，我们只需要遍历到区间的平方根的地方就好了
比如 2 -16 的话
我们只需要遍历到 2 -4
2-100 的话
我们只需要遍历到 2 -10

好，我们拿到了 1 -100000 的所有的素数

我们再次遍历一次 1 -100000，判断每一个数是不是 2017 的相似数
用累积和的求法，算出从 1 到遍历点 i 的相似数的个数

具体就是如果 i 为 2017 的相似数，
那么
1 到 i 的 2017 相似数的个数 = 1 到（i-1）的 2017 相似数的个数 + 1

具体就是如果 i 不是 2017 的相似数，
那么
1 到 i 的 2017 相似数的个数 = 1 到（i-1）的 2017 相似数的个数

最后对于区间 (li,ri) 内 2017 相似数的个数的统计 =
1 到 ri 的 2017 相似数的个数 – 1 到 (li-1) 的 2017 相似数的个数

代码

import math


def sushu(n):
    arr = []
    for i in range(2, n + 1):
        arr.append(i)

    limit = int(math.sqrt(n)) + 1

    prev = []
    while True:
        start = arr[0]
        prev.append(start)
        if start > limit:
            break
        brr = []
        for i in arr:
            if i % start != 0:
                brr.append(i)
        arr = brr

    prev.extend(arr)
    return prev


n = 100000
shushu = sushu(100000)

marks = []
for i in range(n + 1):
    marks.append(False)

for j in shushu:
    marks[j] = True

marks2 = []
result = []
for i in range(n + 1):
    if i % 2 == 0:
        marks2.append(False)
        if i == 0:
            result.append(0)
        else:
            result.append(result[i - 1])
    else:
        if marks[(i + 1) // 2] and marks[i]:
            marks2.append(True)
            result.append(result[i - 1] + 1)
        else:
            marks2.append(False)
            result.append(result[i - 1])

Q = int(input())

ARR = []

for i in range(Q):
    ARR.append(list(map(int, input().split())))

for i in range(Q):
    start = ARR[i][0]
    end = ARR[i][1]
    print(result[end] - result[start - 1])

总结
这道题考察了对素数的求法。运用素数筛选法可以求出某一个区间以内的所有的素数

另外考察了累积和的运用

※ 另外，我会在我的微信个人订阅号上推出一些文章，欢迎关注

退出移动版