競プロ初中級者100問

ABC084D - 2017-like Number

この記事で使うアルゴリズム

エラトステネスの篩

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc084/tasks/abc084_d

この問題では高速な素数判定法が求められます。そこで、エラトステネスの篩を実装します。

解法1

公式の解説pdfにある通りです。

方針

  1. 素数の表を作る
  2. 2017に似た数の表を作る
  3. 累積和を求める

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
N = 10**6
dp = [1] * (N+1)
dp[0] =  dp[1] =  0

for i in range(2,N+1):
    if dp[i]:
        for j in range(i*i, N+1, i):
            dp[j] = 0
like2017 = [0] * (N+1)
for n in range(N+1):
    if dp[n]==0:
        continue
    query = (n+1)//2
    if dp[query]==1:
        like2017[n] = 1


for n in range(N):
    like2017[n+1] += like2017[n]

Q = int(input())
for q in range(Q):
    l, r = map(int,input().split())
    print (like2017[r]-like2017[l-1])

解法2

2017に似た数のリストを用意し、二分探索を行っても十分に間に合います。実装の複雑さなどを考えても、解法1が良いと思います。

方針

  1. 素数のリストを作る
  2. 2017に似た数のリストを作る
  3. 二分探索を行う
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
import bisect
N = 10**6
dp = [1] * (N+1)
dp[0] =  dp[1] =  0
prime = []
for i in range(2,N+1):
    if dp[i]:
        for j in range(i*i, N+1, i):
            dp[j] = 0
for n in range(N+1):
    if dp[n]:
        prime.append(n)

like2017 = []
for p in prime:
    query = (p+1)//2
    idx = bisect.bisect_left(prime, query)
    if prime[idx] == query:
        like2017.append(p)
    
Q = int(input())
for q in range(Q):
    l, r = map(int,input().split())
    l = bisect.bisect_left(like2017, l)
    r = bisect.bisect_right(like2017, r)
    print (r-l)

記事情報

  • 投稿日：2020年4月29日
  • 最終更新日：2020年5月8日