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
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
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の未定義領域にアクセスすると例外
Author And Source
この問題について(Ruby と Python で解く AtCoder ABC084 D 素数 累積和), 我々は、より多くの情報をここで見つけました https://qiita.com/superrino130/items/4a9207395b84d2dd8abe著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .