情報交換概論 第 4 回 (マークアップ言語 / 読み上げソフトのしくみ) 「素数のもとめかた」 講義ノート目次

暗号に必要な素数について調べておこう。 素数 prime number とは、1 とそれ自身でしか割り切れない数のことである。 dtd_primenumber.rb

#!/usr/koeki/bin/ruby
# -*- coding: euc-jp -*-

def primeno(m)
  pn = [2, 3]  # 素数は 2 から開始
  flag = 0
  3.step(m, 2){|l|
    2.upto(Math.sqrt(l).to_i){|i|
      flag = 1
      if (l.divmod(i)[1] == 0)
        flag = 0
        break
      end    
    }
    unless flag == 0
      pn << l
    end
  }
  return pn  # 素数の配列を返す
end

k = 1000
printf("%d までの素数: ", k)
prime = primeno(k)
prime.each{|i|
  printf("%4s", i)
}
printf("\n素数の数 %d 個\n", prime.length)