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

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 [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
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
``````