練習のための問題は 競技プログラミングの履歴
数論
整数の性質とか、素数とか、そのへんはここにまとめる
エラトステネスの篩
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