Je souhaite effectuer une factorisation prime rapide avec Ruby (ABC177E)

référence

https://atcoder.jp/contests/abc177/editorial/82 (Je pense que l'article n'a pas de sens jusqu'à ce que vous lisiez ceci)

Sujet principal

Étant donné un grand nombre de nombres inférieurs ou égaux à A, lorsque vous voulez les factoriser en facteurs premiers Tamisez les Eratostènes et ajoutez le nombre qui a été tamisé. Facilité de factorisation prime

cache = {key(Sa valeur) => value(Le plus petit facteur premier qui a éliminé la clé) }

C'est une histoire qu'il est facile de faire un cache comme celui-ci.

Exemple) Lors de la factorisation de 100 en facteurs premiers

cache[100] 
#=> 2 =Diviser par 2
cache[100/2]
#=> 2 =Diviser par 2
cache[50/2] 
#=> 5 =Diviser par 5
cache[25/5] 
#=> 5 =Diviser par 5

#∴ 100 est divisé par 2 deux fois et 5 deux fois

Si vous créez ce cache, vous pouvez effectuer une factorisation première avec O (logN). Cette fois, j'ai essayé de créer une classe qui peut accélérer la factorisation prime en utilisant ceci, donc Je voudrais comparer les performances avec le [Integer # prime_division] existant (https://docs.ruby-lang.org/ja/latest/method/Integer/i/prime_division.html).

Ce que j'ai fait

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

<détails> <résumé> Code source </ résumé>

#Je veux énumérer les nombres premiers avec un tamis Elatostines et effectuer une factorisation premier à grande vitesse!
# ref: https://atcoder.jp/contests/abc177/editorial/82
class PrimeDivWithSieve
  def initialize(n)
    @sieve = [] #Entrez des nombres premiers jusqu'à n
    @min_div = {} #Entrez le facteur premier minimum de la valeur de clé
    #Le nombre premier qui peut être éliminé peut aller jusqu'à sqrt
    (2..Math.sqrt(n).floor).each do |i|
      next if @min_div[i] #Il y a une valeur ici=Ont été éliminés
      @sieve << i #Si tu viens sans être tamisé, c'est un nombre premier

      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_Essayez de renvoyer la même valeur que la 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] #Renvoie immédiatement lorsqu'il s'agit d'un nombre premier

    return_array = [] # [[a, x], [b, y]] <=> num = a^x * b^y
    while num > 1 do
      prime = @min_div[num] #Facteur premier minimum, nil =>num est un nombre premier
      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

Comparaison des performances

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

N = 1_000_000
times = N/25 #Nombre de 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)

C'est subtil si le nombre de caisses est petit, mais il semble qu'il soit plus rapide d'utiliser le tamis à mesure que le nombre de caisses augmente.

ABC177E

https://atcoder.jp/contests/abc177/submissions/16390851 Je l'ai soumis parce que je pensais gagner, mais un TLE n'a jamais disparu. Je n'ai pas besoin d'informations sur le nombre de fois où il se cassera cette fois, alors Il a été décidé que je devrais prendre note des facteurs premiers de la valeur lors de la fabrication d'un tamis. Exemple) 100 => [2,5], 99 => [3, 11]

https://atcoder.jp/contests/abc177/submissions/16391235 Je suis passé par là. (C'est différent de la factorisation prime haute vitesse cette fois, alors veuillez l'utiliser comme bonus)

Calculez le facteur premier de chaque valeur jusqu'à n (avec tamis) https://github.com/k-karen/ruby-samples/blob/master/sieve/enum_elments.rb

<détails>

Code source </ summary>

#Calculer uniquement les facteurs premiers jusqu'à 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