素数判定 - ohbarye

素数判定

$ N を$ 2,3,4,5,6,..,\sqrt{N} で割って、どれでも割れなければ素数

計算量は$ O(\sqrt N)

RubyではビルトインのPrime moduleがある

中身 https://github.com/ruby/ruby/blob/46b93175ed9fe061f309fe5538f23dc13aa1de0b/lib/prime.rb#L38 を見ると平方根を上限に計算している

code:ruby

require 'prime'

Prime.prime? 10**9 + 7

# => true