FreeStyleWiki

数論

[アルゴリズム,数論]

練習のための問題は 競技プログラミングの履歴

数論

整数の性質とか、素数とか、そのへんはここにまとめる

  エラトステネスの篩

100万以下のすべての素数を列挙してみる

def erastosthenes(n)
  array = (2..n).to_a
  threshold = Math.sqrt(n)
  count = 2
  while threshold > count
    array.reject!{|n| n != count and n % count == 0}
    count += 1
  end
  array
end

PN = erastosthenes(1000000)

puts PN.length
puts PN[10000]

  約数の高速な算出

def make_divisors(n)
    divisors = []
    for i in 1..((n**0.5)+1).to_i
        if n % i == 0
            divisors << i
            if i != n / i
                divisors << n/i
            end
        end
    end
    divisors.uniq.sort
end

  素因数分解

def trial_division_sqrt(n)
  prime_count = Array.new(n+1, 0)
  
  for i in 2..(Math.sqrt(n).to_i+2)
    while n%i==0
      n /= i
      prime_count[i] += 1
    end    
  end
  prime_count[n] += 1 if n>1
  prime_count
end