AtCoder Beginner Contest D - 2017-like Number Difficulty: 981
This theme, prime number + cumulative sum
Speaking of prime numbers, *** Ruby *** has a Prime library.
Put a prime number less than or equal to 100000 in the hash, check if (n + 1) / 2 is in the hash, and get a number similar to 2017.
Next, find the appearance of a number similar to 2017 by the cumulative sum.
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
Use a prime number generator.
rui.rb
1.upto(100000) do |i|
k[i] += k[i - 1]
end
We are getting the cumulative sum. 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
I make my own prime numbers.
hash.py
if (key + 1) / 2 in h and h[(key + 1) / 2] == 1:
k[key] = 1
It is necessary to confirm the existence of the dictionary key.
| Ruby | Python | |
|---|---|---|
| Code length(Byte) | 344 | 697 |
| Execution time(ms) | 288 | 692 |
| memory(KB) | 4304 | 7896 |
Referenced site
Recommended Posts