Ich möchte mit Ruby (ABC177E) eine schnelle Primfaktorisierung durchführen.

Referenz

https://atcoder.jp/contests/abc177/editorial/82 (Ich denke, der Artikel ist bedeutungslos, bis Sie dies lesen)

Hauptthema

Bei einer großen Anzahl von Zahlen kleiner oder gleich A, wenn Sie sie in Primfaktoren zerlegen möchten Sieben Sie die Eratostenes und fügen Sie die Zahl hinzu, die gesiebt wurde. Einfach für die Primfaktorisierung

cache = {key(Dessen Wert) => value(Der kleinste Primfaktor, der den Schlüssel abgesiebt hat) }

Es ist eine Geschichte, dass es einfach ist, einen solchen Cache zu erstellen.

Beispiel) Wenn 100 in Primfaktoren berücksichtigt werden

cache[100] 
#=> 2 =Teilen Sie durch 2
cache[100/2]
#=> 2 =Teilen Sie durch 2
cache[50/2] 
#=> 5 =Teilen Sie durch 5
cache[25/5] 
#=> 5 =Teilen Sie durch 5

#∴ 100 wird zweimal durch 2 und zweimal durch 5 geteilt

Wenn Sie diesen Cache erstellen, können Sie die Primfaktorisierung mit O (logN) durchführen. Dieses Mal habe ich versucht, eine Klasse zu erstellen, die die Primfaktorisierung damit beschleunigen kann Ich möchte die Leistung mit der vorhandenen Integer # prime_division vergleichen.

Was ich gemacht habe

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

Quellcode

#Ich möchte Primzahlen mit einem Elatostines-Sieb aufzählen und die Primfaktorisierung mit hoher Geschwindigkeit durchführen!
# ref: https://atcoder.jp/contests/abc177/editorial/82
class PrimeDivWithSieve
  def initialize(n)
    @sieve = [] #Geben Sie Primzahlen bis n ein
    @min_div = {} #Geben Sie den minimalen Primfaktor des Schlüsselwerts ein
    #Die Primzahl, die herausgefiltert werden kann, kann bis zu sqrt sein
    (2..Math.sqrt(n).floor).each do |i|
      next if @min_div[i] #Hier gibt es einen Wert=Wurden ausgesiebt
      @sieve << i #Wenn Sie kommen, ohne gesiebt zu werden, ist es eine Primzahl

      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_Versuchen Sie, den gleichen Wert wie Division zurückzugeben
  # https://docs.ruby-lang.org/ja/latest/method/Integer/i/prime_division.html
  def prime_division(num)
    return [[num, 1]] if !@min_div[num] #Gibt sofort zurück, wenn es sich um eine Primzahl handelt

    return_array = [] # [[a, x], [b, y]] <=> num = a^x * b^y
    while num > 1 do
      prime = @min_div[num] #Minimaler Primfaktor, nil =>num ist eine Primzahl
      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

Leistungsvergleich

(Vollständiger Testcode) [https://github.com/k-karen/ruby-samples/blob/master/sieve/bench_prime_division.rb]

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

Es ist subtil, wenn die Anzahl der Fälle gering ist, aber es scheint, dass es schneller ist, das Sieb zu verwenden, wenn die Anzahl der Fälle zunimmt.

ABC177E

https://atcoder.jp/contests/abc177/submissions/16390851 Ich habe es eingereicht, weil ich dachte, ich würde gewinnen, aber ein TLE ist nie verschwunden. Ich brauche keine Informationen darüber, wie oft es diesmal kaputt gehen wird Es wurde beschlossen, die Hauptfaktoren zu notieren, die der Wert bei der Herstellung eines Siebs hat. Beispiel) 100 => [2,5], 99 => [3, 11]

https://atcoder.jp/contests/abc177/submissions/16391235 Ich ging daran vorbei. (Diesmal unterscheidet es sich von der Hochgeschwindigkeits-Primfaktorisierung. Verwenden Sie sie daher bitte als Bonus.)

Berechnen Sie den Primfaktor jedes Wertes bis zu n (mit Sieb) https://github.com/k-karen/ruby-samples/blob/master/sieve/enum_elments.rb

Quellcode

#Berechnen Sie nur Primfaktoren bis 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