共计 1967 个字符,预计需要花费 5 分钟才能阅读完成。
本文章为原创文章,未经过允许不得转载
运行要求
运行时间限制: 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])
总结
这道题考察了对素数的求法。运用素数筛选法可以求出某一个区间以内的所有的素数
另外考察了累积和的运用
※ 另外,我会在我的微信个人订阅号上推出一些文章,欢迎关注