メイドちゃんの素因数分解のとこだけ抜き出したもの

factorization.rb

def powm(base, power, mod)
  ret = 1
  until power == 0
    ret = ret * base % mod if power & 1 == 1
    base = base * base % mod
    power >>= 1
  end
  ret
end

def probab_prime(n, k)
  return true if n == 2
  return false if n == 1 || n & 1 == 0
  d = n - 1
  d >>= 1 while d & 1 == 0
  k.times do
    y = powm(rand(n - 2) + 1, d, n)
    t = d
    until t == n - 1 || y == 1 || y == n - 1
      y = y * y % n
      t <<= 1
    end
    return false if y != n - 1 && t & 1 == 0
  end
  return true
end

def next_prime(p)
  n = p + 1
  n += 1 while !probab_prime(n, 10)
  return n
end

def factor_pm1(n0)
  pa = []
  ca = []
  if probab_prime(n0, 10)
    pa << n0
  else
    ca << n0
  end
  while !ca.empty?
    n = ca.shift
    m = 3
    p = 2
    while n % (f = p) != 0
      f *= f while f < 1000
      m = powm(m, f, n)
      f = n.gcd(m - 1)
      break if f > 1 && f < n
      p = next_prime(p)
    end
    if probab_prime(f, 10)
      pa << f
    else
      ca << f
    end
    if f < n
      f = n / f      
      if probab_prime(f, 10)
        pa << f
      else
        ca << f
      end
    end
  end
  return pa.sort
end

def factor_array_to_str(f)
  result = nil
  factor = ""
  if f.length == 1
    factor = nil
    result = true
  else
    p = nil
    c = 1
    f.each_with_index { |v, i|
      if p == v
        c += 1
        next if i + 1 != f.length
      elsif p
        factor << "#{factor.empty? ? '' : '*'}#{p}#{c == 1 ? '' : '^' + c.to_s}"
        c = 1
      end
      p = v
      if i + 1 == f.length
        factor << "#{factor.empty? ? '' : '*'}#{p}#{c == 1 ? '' : '^' + c.to_s}"
      end
    }
    result = false
  end
  return result, factor
end

def factor_pm1_ruby(int)
  begin
    f = nil
    timeout(60) {
      f = factor_pm1(int)
    }
    p f
    return factor_array_to_str(f)
  rescue TimeoutError => e
    puts "==== timeout: #{e}"
    return nil, nil
  rescue Exception => e
    say("CHECK PRIME ERROR: #{e}", "e")
  end
end

puts factor_pm1_ruby(ARGV[0].to_i)