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

reference

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

cache[100] 
#=> 2 =Divide by 2
cache[100/2]
#=> 2 =Divide by 2
cache[50/2] 
#=> 5 =Divide by 5
cache[25/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

https://github.com/k-karen/ruby-samples/blob/master/sieve/prime_div_with_sieve.rb

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
      end
    end
    (Math.sqrt(n).floor.next..n).each do |i|
      next if @min_div[i]
      @sieve << i
    end
  end

  # 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 !@min_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
      end
      return_array.push([prime, div_total])
    end

    return_array
  end

  def prime_list
    @sieve
  end
end

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|
      ans1.push(divisor.prime_division(i))
    end
  end

  r.report 'PrimeDiv' do
    TESTCASES.each do |i|
      ans2.push(i.prime_division)
    end
  end
end

# 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.

ABC177E

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].push(i)
        else
          @elements[sieve_target] = [i]
        end
        sieve_target += i
      end
    end
  end

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