3792. 质数问题
摘要
Title: 3792. 质数问题
Tag: 线性筛
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
3792. 质数问题
-
题意
给定两个整数 n和 k，请你判断在 [2,n]的范围内是否存在不少于 k个质数，满足可以表示为两个相邻质数与 1的和。
例如，19满足条件，因为 19=7+11+1。 -
思路
打表后前缀和判断
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49'''
Author: NEFU AB-IN
Date: 2023-03-19 20:16:20
FilePath: \Acwing\3792\3792.py
LastEditTime: 2023-03-19 20:33:25
'''
read = lambda: map(int, input().split())
from collections import Counter, deque
from heapq import heappop, heappush
from itertools import permutations
N = int(1e3 + 10)
INF = int(2e9)
st, prime = [0] * N, []
vis = [0] * N
cnt = 0
def init():
for i in range(2, N):
if st[i] == 0:
prime.append(i)
j = 0
while prime[j] * i < N:
st[prime[j] * i] = 1
if i % prime[j] == 0:
break
j += 1
init()
for i in range(len(prime) - 1):
num = prime[i] + prime[i + 1] + 1
if num > N:
break
if st[num] == 0:
vis[num] = 1
# print(st)
for i in range(1, N):
vis[i] += vis[i - 1]
for _ in range(int(input())):
n, k = read()
# print(vis[n])
print("YES" if vis[n] >= k else "NO")