rubyで素数かどうかを調べる方法
背景
とある練習問題で、ある自然数nが素数かどうかを調べる方法を求めなさいという問題があり、自分なりに解いてみた方法です。
そもそも素数とは?
素数(そすう、英: primeあるいはprime number)とは、2 以上の自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。(引用:ウィキペディア(Wikipedia))
つまり1以外の自然数で自然数nを1と自然数nでしか割り切れない自然数が素数となるということです。
考え方
ではnが素数かどうかを調べるにはどうすればいいのか?
考え方としては、1とn以外にもnを割り切れる数があればnは素数ではなく、割り切れる数が他にない場合はnは素数であると言えると思います。
なのでnを2からnより小さい最大数まで一つずつ割っていき、割り切れる数、つまり余り0の数があった場合は素数ではなく、どの数でも割り切れなかった場合は素数となります。
※1は素数であってもnを割り切れる数なので、2から割り切れるか検証します
※nより大きい数は素数であってもなくてもnを割り切れないので検証対象ではありません
※n自身は素数であってもnを割り切れる数なので検証対象ではありません
実際のコード
言葉にするとややこしいので実際にコードにしてみます
puts "素数かどうか調べます。調べたい自然数を入力してください"
# 変数nが調べたい数字となります
n = gets.to_i
# 自然数でない値が入力された場合、再入力させます
if n == 0
while n == 0
puts "自然数を入力してください"
n = gets.to_i
end
end
# 素数の定義として「2以上の自然数で、正の約数が1と自分自身のみであるもの」とあるので、1が入力された場合は素数ではないというメッセージを表示します
if n == 1
puts "1は素数ではありません"
return
end
# 2からnより小さい最大数まで調べたいのでいったん2を変数iに代入します
i = 2
# iがnより小さい最大数になるまでnをiで割っていきます
while i < n
# nがiで割り切れるかを検証します
if n % i == 0
#割り切れた場合は素数ではないというメッセージが表示されその時点で処理が停止されます
puts "#{n}は素数ではありません"
return
end
#iに1を足します
i += 1
end
#returnで処理が終了しなかった場合素数であるというメッセージが表示されます
puts "#{n}は素数です"
これでnが素数かどうか調べることができました。
終わりに
とりあえずQiitaにアカウント登録してから初めての投稿なので、テストと思いつつの投稿です。
内容としては、自分が解いた練習問題の模範回答があまりしっくり来なかったので自分なりの解き方を提示してみました。
基本これまでrubyしか学んできていないのですが、アルゴリズムの問題は言語が変わっても活かせるものかなと思うので引き続き取り組んでいきたいと思います。