練習のための問題は 競技プログラミングの履歴
数論
整数の性質とか、素数とか、そのへんはここにまとめる
エラトステネスの篩
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]
約数の高速な算出
- プロジェクトオイラーでやたら約数の問題が出るので
- 約数を高速で列挙するコード(Python) をRubyに翻訳
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