Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers

Introduction

This theme

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

Summary

Referenced site

Recommended Posts

Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum
Solving with Ruby and Python AtCoder ABC151 D Breadth-first search
Solving with Ruby and Python AtCoder ABC138 D Adjacency list
Solve AtCoder ABC168 with python (A ~ D)
Solving with Ruby, Python and networkx AtCoder ABC168 D Adjacency list
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
Solving with Ruby and Python AtCoder ABC057 C Prime Factorization Bit Search
Solving with Ruby, Perl, Java, and Python AtCoder ARC 098 C Cumulative sum
Solving with Ruby, Perl, Java and Python AtCoder ABC 165 D Floor function
Solving with Ruby and Python AtCoder Tenka1 Programmer Contest C Cumulative sum
Solving with Ruby, Perl, Java and Python AtCoder ABC 131 D Array Sorting
AtCoder ABC172 C Cumulative Sum Binary Search Solved by Ruby and Python
Solve with Ruby, Perl, Java and Python AtCoder ABC 047 C Regular Expression
Solve AtCoder ABC 186 with Python
Solve ABC166 A ~ D with Python
Solving with Ruby and Python AtCoder AISING2020 D Iterative Squares
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
Solving with Ruby and Python AtCoder ARC067 C Prime Factorization
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
Solving with Ruby, Python and numpy AtCoder ABC054 B Matrix operation
Solving with Ruby, Perl, Java, and Python AtCoder ABC 065 C factorial
AtCoder JSC2019 Qual B to solve with Ruby and Python Inverse element of arithmetic progression
Solving with Ruby, Perl, Java and Python AtCoder CADDi 2018 C Prime Factorization
Project Euler # 10 "sum of prime numbers" in Python
Solve A ~ D of yuki coder 247 with python
[AtCoder explanation] Control the A, B, (C), D problems of ABC165 with Python!
[AtCoder explanation] Control the A, B, C, D problems of ABC183 with Python!
[AtCoder explanation] Control the A, B, C, D problems of ABC181 with Python!
Comparison of CoffeeScript with JavaScript, Python and Ruby grammar
Version control of Node, Ruby and Python with anyenv
Determine prime numbers with python
Solve ABC175 D in Python
AtCoder ABC 182 Python (A ~ D)
Solving with Ruby and Python AtCoder ARC 059 C Least Squares
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 A
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 B
AtCoder ABC168 A case expression solved in Ruby and Python
Project Euler 10 "Sum of Prime Numbers"
Solve Atcoder ABC169 A-D in Python
Solve AtCoder Problems Recommendation with python (20200517-0523)
Solve ABC168 A ~ C with Python
Solved AtCoder ABC 114 C-755 with Python3
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
Solve ABC158 A ~ C with Python
Coexistence of Python2 and 3 with CircleCI (1.0)
I compared the speed of Hash with Topaz, Ruby and Python
I tried to create a list of prime numbers with python
I wanted to solve the ABC164 A ~ D problem with Python
ABC 157 D --Solve Friend Suggestions in Python!
[AtCoder explanation] Control the A, B, C problems of ABC186 with Python!
Solving with Ruby, Perl, Java, and Python AtCoder AGC 033 A Breadth-first search
Algorithm learned with Python 4th: Prime numbers
I wanted to solve ABC160 with Python
[AtCoder explanation] Control the A, B, C problems of ABC185 with Python!
[Python] Solve 10 past elite problems of Atcoder
Solve AtCoder Beginner Contest 170 D --Not Divisible (ABC170D) with python (Eratosthenes sieve)