素因数分解するやつ。"ruby pm1.rb 12345678987654321"

pm1.rb

# encoding: utf-8

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 pm1(n0)
  pa = []
  ca = []
  probab_prime(n0, 10) ? pa << n0 : ca << n0
  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
    probab_prime(f, 10) ? pa << f : ca << f
    if f < n
      f = n / f      
      probab_prime(f, 10) ? pa << f : ca << f
    end
  end
  return pa.sort
end

p pm1(ARGV[0].to_i)