I want to perform high-speed prime factorization in Ruby (ABC177E)


https://atcoder.jp/contests/abc177/editorial/82 (I think the article is meaningless until you read this)

Main subject

Given a large number of numbers less than or equal to A, when you want to factor them into prime factors Sieve of Eratosthenes and then add the number that was sifted. Easy when factoring into prime factors

cache = {key(Its value) => value(The smallest prime factor that sifted off the key) }

It is a story that it is easy to make a cache like this.

Example) When factoring 100 into prime factors

#=> 2 =Divide by 2
#=> 2 =Divide by 2
#=> 5 =Divide by 5
#=> 5 =Divide by 5

#∴ 100 is divided by 2 twice and 5 twice

It is said that if you create this cache, you can perform prime factorization with O (logN). This time, I used this to create a class that can speed up prime factorization. I would like to compare the performance with the existing Integer # prime_division.

What I made


Source code
#I want to enumerate prime numbers with an Eratosthenes sieve and factor them at high speed!
# ref: https://atcoder.jp/contests/abc177/editorial/82
class PrimeDivWithSieve
  def initialize(n)
    @sieve = [] #Enter prime numbers up to n
    @min_div = {} #Enter the smallest prime factor of the key value
    #The prime numbers that can be screened out can be up to sqrt
    (2..Math.sqrt(n).floor).each do |i|
      next if @min_div[i] #There is a value here=Have been screened out
      @sieve << i #If it comes without being sifted, it's a prime number

      sieve_target = i * i
      while sieve_target <= n do
        @min_div[sieve_target] ||= i
        sieve_target += i
    (Math.sqrt(n).floor.next..n).each do |i|
      next if @min_div[i]
      @sieve << i

  # Integer#prime_Try to return the same value as division
  # https://docs.ruby-lang.org/ja/latest/method/Integer/i/prime_division.html
  def prime_division(num)
    return [[num, 1]] if [email protected]_div[num] #Returns immediately when it is a prime number

    return_array = [] # [[a, x], [b, y]] <=> num = a^x * b^y
    while num > 1 do
      prime = @min_div[num] #Minimum prime factor, nil =>num is a prime number
      break return_array.push([num, 1]) if !prime

      div_total = 0
      while num % prime == 0 do
        num /= prime
        div_total += 1
      return_array.push([prime, div_total])


  def prime_list

Performance comparison

(Full test code) [https://github.com/k-karen/ruby-samples/blob/master/sieve/bench_prime_division.rb]

N = 1_000_000
times = N/25 #Number of tests
TESTCASES = (1..N).to_a.sample(times)
require 'prime'

ans1 = []
ans2 = []
Benchmark.bm 10 do |r|
  r.report 'MyDivsor' do
    divisor = PrimeDivWithSieve.new(N)
    TESTCASES.each do |i|

  r.report 'PrimeDiv' do
    TESTCASES.each do |i|
# times = N/25 (40,000)
# Result
# user     system      total        real
# MyDivsor     0.875262   0.032392   0.907654 (  0.926605)
# PrimeDiv     0.849263   0.012468   0.861731 (  0.879886)

# times = N/2 (500,000)
# Result
# user     system      total        real
# MyDivsor     1.659268   0.058786   1.718054 (  1.758668)
# PrimeDiv    10.787444   0.118755  10.906199 ( 11.071594)

It is subtle if the number of cases is small, but it seems that it is faster to use a sieve as the number of cases increases.


https://atcoder.jp/contests/abc177/submissions/16390851 I submitted it because I thought I would win, but one TLE never disappeared. I don't need information about how many times it will break this time, so It was decided that I should make a note of the prime factors that the value has when making a sieve. Example) 100 => [2,5], 99 => [3, 11]

https://atcoder.jp/contests/abc177/submissions/16391235 I passed by this. (It's different from the high-speed prime factorization this time, so please give it as a bonus)

Calculate the prime factors of each value up to n (with sieve) https://github.com/k-karen/ruby-samples/blob/master/sieve/enum_elments.rb

Source code
#Calculate only prime factors up to n
class EnumElements
  def initialize(n)
    @sieve = []
    @elements = {}
    (2..n).each do |i|
      next if @elements[i]
      @sieve << i
      @elements[i] = [i]

      sieve_target = i * 2
      while sieve_target <= n do
        if @elements[sieve_target]
          @elements[sieve_target] = [i]
        sieve_target += i

  def elements(num)
    @elements[num] || []

Recommended Posts

I want to perform high-speed prime factorization in Ruby (ABC177E)
I want to use arrow notation in Ruby
I want to get the value in Ruby
I want to create a Parquet file even in Ruby
[Ruby] I want to put an array in a variable. I want to convert to an array
[Java] I want to perform distinct with the key in the object
I want to change the value of Attribute in Selenium of Ruby
I want to use @Autowired in Servlet
[Ruby] I want to output only the odd-numbered characters in the character string
[Ruby] I want to display posted items in order of newest date
I want to sort by tab delimited by ruby
[Ruby] I want to do a method jump!
I want to pass APP_HOME to logback in Gradle
rsync4j --I want to touch rsync in Java.
[Xcode] I want to manage images in folders
I want to be eventually even in kotlin
I wrote a prime factorization program in Java
I want to perform aggregation processing with spring-batch
I want to use Combine in UIKit as well.
I want to use Clojure's convenient functions in Kotlin
I want to use fish shell in Laradock too! !!
I want to use ES2015 in Java too! → (´ ・ ω ・ `)
I want to use a little icon in Rails
I want to define a function in Rails Console
I want to stop snake case in table definition
I want to click a GoogleMap pin in RSpec
[Ruby on Rails] I want to get the URL of the image saved in Active Storage
I want to find a relative path in a situation using Path
I want to set the conditions to be displayed in collection_check_boxes
I want to convert characters ...
What I did in the version upgrade from Ruby 2.5.2 to 2.7.1
Even in Java, I want to output true with a == 1 && a == 2 && a == 3
I want to transition to the same screen in the saved state
[Ruby] I want to reverse the order of the hash table
I want to simplify the conditional if-else statement in Java
[Wire Mock] I want to set up a stub / mock server in Java and perform E2E tests.
Webpack and webpacker I want to tell Ruby people right now
I want to add a browsing function with ruby on rails
I tried to write code like a type declaration in Ruby
I want to get some properties as JSON strings in Jackson!
I want to display the images under assets/images in the production environment
I want to add devise in Rails, but I can't bundle install
I want to remove the top margin in Grouped UITableView (swift)
I tried to make Numeron which is not good in Ruby
I want to perform asynchronous processing and periodic execution with Rail !!!
[Android] I want to get the listener from the button in ListView
Swift: I want to chain arrays
How to iterate infinitely in Ruby
Try to implement Yubaba in Ruby
I want to use FormObject well
I want to convert InputStream to String
How to install Bootstrap in Ruby
I want to docker-compose up Next.js!
I tried to make a parent class of a value object in Ruby
[Rails] I want to send data of different models in a form
I want to write JSP in Emacs more easily than the default.
I want to select multiple items with a custom layout in Dialog
(Limited to Java 7 or later) I want you to compare objects in Objects.equals
[Ruby] I want to extract only the value of the hash and only the key
[Note] I want to get in reverse order using afterLast with JdbcTemplate
I tried to solve the tribonacci sequence problem in Ruby, with recursion.