Ruby と Python で解く AtCoder ABC084 D 素数 累積和

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Beginner Contest D - 2017-like Number
Difficulty: 981

今回のテーマ、素数 ＋ 累積和

素数と言えばRubyにはPrimeライブラリがあります。
100000以下の素数をハッシュに入れ、(n + 1) / 2がハッシュにあるかどうかを確認して、2017に似た数を取得します。
次に、2017に似た数の出現を累積和で求めます。

Ruby

ruby.rb

require 'prime'

g = Prime::EratosthenesGenerator.new
h = Hash.new(0)
a = 2
while a < 100000
  h[a] = 1
  a = g.next
end
k = Array.new(100001, 0)
h.keys.each do |x|
  k[x] = 1 if h[(x + 1) / 2] == 1
end
1.upto(100000) do |i|
  k[i] += k[i - 1]
end
gets.to_i.times do
  l, r = gets.split.map(&:to_i)
  puts k[r] - k[l - 1]
end

prime.rb

g = Prime::EratosthenesGenerator.new

素数の生成器を使用します。

rui.rb

1.upto(100000) do |i|
  k[i] += k[i - 1]
end

累積和を取得しています。

Python

python.py

from sys import stdin

def main():
    from collections import defaultdict
    from math import sqrt
    input = stdin.readline

    h = defaultdict(int)
    h[2] = 1
    for i in range(3, 100000, 2):
        for j in range(3, int(sqrt(i)) + 1, 2):
            while i % j == 0:
                h[j] = 1
                i //= j
        if i > 1:
            h[i] = 1
    k = [0] * 100001
    for key in h.keys():
        if (key + 1) / 2 in h and h[(key + 1) / 2] == 1:
            k[key] = 1
    for i in range(1, 100001):
        k[i] += k[i - 1]
    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        print(k[r] - k[l - 1])
main()

prime.py

    h[2] = 1
    for i in range(3, 100000, 2):
        for j in range(3, int(sqrt(i)) + 1, 2):
            while i % j == 0:
                h[j] = 1
                i //= j
        if i > 1:
            h[i] = 1

素数生成は自作しています。

hash.py

        if (key + 1) / 2 in h and h[(key + 1) / 2] == 1:
            k[key] = 1

辞書のキーの存在確認が必要です。

	Ruby	Python
コード長 (Byte)	344	697
実行時間 (ms)	288	692
メモリ (KB)	4304	7896

まとめ

• ABC 084 D を解いた
• Ruby に詳しくなった
• Python に詳しくなった

参照したサイト
ループ中にdefaultdictの未定義領域にアクセスすると例外