素数

新しいvista版のタブレットPC、hp compac tc4400の型番GC953PA#ABJの953が素数かどうか、を調べるのに以前大きな数の素因数分解http://d.hatena.ne.jp/niming538/20070301で使ったrubyプログラムを使いました。

まったくのスクラッチからどうするかという手順です。

1.つぎのサイトhttp://rubyinstaller.rubyforge.org/からrubywindows用のワンクリックインストーラーをダウンロードし、インストールする。10分。
2.付属してくるエディターのsciteを立ち上げ、下記のプログラムをカットアンドペーストする。1分。
3.f5で実行ですが、その前にファイル名(factor.rb)とかつけて保存しないと動かないので、保存する。そして実行。3秒。

トータル15分くらいで、好きな数の素因数分解ができて、天国にいる気分。

def primes_up_to(n) # calculate all the primes up to the number
  r = (2..n).to_a # convert to an array
  primes =[]
  while r.first**2 < n # up to square root
    primes.push(r.first)
    r.reject! { |i| i % primes.last == 0} # sieve
  end
  primes + r # the rest are primes
end

def factor(n) # factorization in prime numbers
  factors = {}
  for p in primes_up_to((n**0.5).ceil) # up to square root
    while n % p == 0
      factors[p] ? factors[p] += 1: factors[p] = 1 # if exist count up else make one
      n /= p # divide the base
    end
  end 
  factors[n] = 1 if n != 1 # if no primes then n => 1 is the answer
  factors
end

i = 953
p factor(i)


追記:2007/05/23
博士の愛した数式小川洋子、で冷蔵庫の番号2311を家政婦のおばさんが手で計算して、「君を素数と認定する」とやってました。4桁の素数確認を手でやる気はしないですが、やるとすると。1.2311のルートを考える(>48,<49。インド人なら暗算?)、2.49までの素数を考える(=>2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,49)、3.これらで2311を割ってどれでも割れないことを確認する。むむぅ、やっぱやる気になりませんね。