0
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

posted at

rubyで約数を算出する

AtCoderにて、与えられた値を階乗したものについて約数の個数を求める問題があったので、解いた際のコードをのっける。

問題

コード

↓パフォーマンスが悪い方(与えられる引数が20超えてくると計算が遅くなるのでほぼほぼ使えない)


# 標準入力の取得
n = gets.to_i

# 階乗の計算
def factorial(n)
  (1..n).inject(:*)
end

def divider(n)
  ans = factorial(n)
  # 1の約数は1のみ
  return 1 if ans == 1
  i = 1
  # 自身も約数になるため始めに入れておく
  arr = [ans]
  while i <= ans / 2
    arr << i if ans % i == 0
    i += 1
  end
  arr.count % 1000000007
end

p divder_advance(n)



↓パフォーマンスが良い方
約数を求める公式を使用しているパターン


require 'prime'

n = gets.to_i

def factorial(ans)
  (1..ans).inject(:*)
end

# 階乗した値を素因数分解し、約数の公式が使用できる形に整形する
def divder_advance(n)
  target = factorial(n)
  return 1 if target == 1
  # arrs内の各要素に対して、1を加え、指数を展開した配列に書き換える
  ans_map = target.prime_division.map do |ary|
    new_arr = (1..ary[1]).map { |i| ary[0]**i }
    new_arr.unshift(1)
  end
  multiple_array_count(ans_map) % 1000000007
end

# [[1,2,4],[1,3,9]]みたいな配列に対して、[1,2,4]の要素数3と[1,3,9]の要素数3を掛けた9を返す
def multiple_array_count(arr)
  arr.map(&:length).inject(:*)
end

p divder_advance(n)

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
0
Help us understand the problem. What are the problem?