AtCoder Beginner Contest D - 2017-like Number Difficulty: 981
Dieses Thema, Primzahl + kumulative Summe
Apropos Primzahlen: *** Ruby *** hat eine Primzahlbibliothek.
Geben Sie eine Primzahl kleiner oder gleich 100000 in den Hash ein, prüfen Sie, ob (n + 1) / 2 im Hash enthalten ist, und erhalten Sie eine Zahl ähnlich 2017.
Als nächstes finden Sie das Aussehen einer Zahl ähnlich wie 2017 durch die kumulierte Summe.
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
Verwenden Sie einen Primgenerator.
rui.rb
1.upto(100000) do |i|
k[i] += k[i - 1]
end
Wir bekommen die kumulative Summe. 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
Ich mache meine eigenen Primzahlen.
hash.py
if (key + 1) / 2 in h and h[(key + 1) / 2] == 1:
k[key] = 1
Es ist erforderlich, das Vorhandensein des Wörterbuchschlüssels zu bestätigen.
| Ruby | Python | |
|---|---|---|
| Codelänge(Byte) | 344 | 697 |
| Ausführungszeit(ms) | 288 | 692 |
| Erinnerung(KB) | 4304 | 7896 |
Referenzierte Site
Recommended Posts