素数について
素数とは、以下の条件を満たす数値です。
- 1より大きい数値 かつ
- 1と自分自身以外の数値では割れない数値。
例
「5」は1と5以外の数値で割れないので素数です。
「6」は1,2,3,6で割れるので素数ではない。
参考：素数の一覧
素数の判定をするアルゴリズム
素数を判定するアルゴリズムはいくつかありますが、単純なアルゴリズムを２つ紹介します。
すべてのパターンを試す判定方法
このアルゴリズムは入力した数値を2から入力した数値未満の数で順番に試し割りを行い、割り切れるかどうか確認する方法です。
割り切れた場合、「1と自分自身以外の数値では割れない数値」に合致しないので、素数ではないと判定できます。判定できた時点で反復処理を終了させます。
入力した数値未満の数で割り切れない場合は素数と判定します。
単純なアルゴリズムですが、割り切れるまで順番に試すので低速です。
偶数を除外する判定方法
奇数と偶数を判定するアルゴリズムで説明したように、偶数は2で割り切れることが分かっています。
よって2の倍数(2,4,6,8…)で割る処理を除外します。
2の倍数を除外するにはカウントアップ用の変数を3で初期化しておき+2ずつカウントアップするようにします。
偶数を除外することによりループ回数が半分になるので、その分速くなります。
サンプルコード
素数を判定するアルゴリズムを以下のプログラミング言語で紹介します。
- Tcl
- Python
サンプルコードについて
各プログラミング言語の基本的な制御構造とデータ構造を使って記述しています。
必要であれば、for, foreach、リスト、配列などに書き換えたり、関数化を行って練習してください。
Tcl
[サンプル：prime-number.tcl]
#!/bin/sh
# the next line restarts using tclsh \
exec tclsh "$0" "$@"
# 素数判定(すべてのパターンを試す)
# num : 数値。
# flag : 素数判定。0:素数。 1:素数ではない。
# i : ループカウンタ。
puts -nonewline "数値を入力してください : "
flush stdout
set num [gets stdin]
set flag 0 ;# 0で初期化。
if {$num < 2} {
set flag 1 ;# 0,1は素数でない為、除外する。
}
# 2以上の数値を判定。
set i 2
while {$i < $num} {
if {$num % $i == 0} {
set flag 1 ;# 割り切れた。
break ;# ループを抜ける。
}
incr i
}
# 判定結果を出力する。
if {$flag == 0} {
puts "$num は素数です。"
} else {
puts "$num は素数ではありません。"
}
[実行例]
$ ./prime-number.tcl 数値を入力してください : 11 11 は素数です。 $ ./prime-number.tcl 数値を入力してください : 12 12 は素数ではありません。
[サンプル：prime-number2.tcl]
#!/bin/sh
# the next line restarts using tclsh \
exec tclsh "$0" "$@"
# 素数判定(偶数を除外する)
# num : 数値。
# flag : 素数判定。0:素数。 1:素数ではない。
# i : ループカウンタ。
puts -nonewline "数値を入力してください : "
flush stdout
set num [gets stdin]
set flag 0 ;# 0で初期化。
# 0,1,2及び偶数の判定
if {$num < 2} {
set flag 1 ;# 0,1は素数でない為、除外する。
} elseif {$num == 2} {
set flag 0 ;# 2は素数。
} elseif {$num % 2 == 0} {
set flag 1 ;# 偶数は素数でない為、除外する。
}
# 3以上の奇数を判定する。
set i 3
while {$i < $num} {
if {$num % $i == 0} {
set flag 1 ;# 割り切れた。
break ;# ループを抜ける。
}
incr i +2
}
# 判定結果を出力する。
if {$flag == 0} {
puts "$num は素数です。"
} else {
puts "$num は素数ではありません。"
}
[実行例]
$ ./prime-number2.tcl 数値を入力してください : 11 11 は素数です。 $ ./prime-number2.tcl 数値を入力してください : 12 12 は素数ではありません。
Python
[サンプル：prime-number.py]
#!/usr/bin/env python3
# 素数判定(すべてのパターンを試す)
# num : 数値。
# flag : 素数判定。0:素数。 1:素数ではない。
# i : ループカウンタ。
num = input('数字を入力してください。: ')
num = int(num) # 文字列から数値に変換
flag = 0 # 0で初期化。
if num < 2:
flag = 1 # 0,1は素数でない為、除外する
# 2以上の数値を判定。
i = 2
while i < num:
if num % i == 0:
flag = 1 # 割り切れた。
break # ループを抜ける。
i += 1
# 判定結果を出力する。
if flag == 0:
print(num,'は素数です。')
else:
print(num,'は素数ではありません。')
[実行例]
$ ./prime-number.py 数字を入力してください。: 11 11 は素数です。 $ ./prime-number.py 数字を入力してください。: 12 12 は素数ではありません。
[サンプル：prime-number2.py]
#!/usr/bin/env python3
# 素数判定(偶数を除外する)
# num : 数値。
# flag : 素数判定。0:素数。 1:素数ではない。
# i : ループカウンタ。
num = input('数字を入力してください。: ')
num = int(num) # 文字列から数値に変換
flag = 0 # 0で初期化。
# 0,1,2及び偶数の判定
if num < 2:
flag = 1 # 0,1は素数でないため除外する。
elif num == 2:
flag = 0 # 2は素数。
elif num % 2 == 0:
flag = 1 # 偶数は素数でないため除外する。
# 3以上の奇数を判定する。
i = 3
while i < num:
if num % i == 0:
flag = 1 # 割り切れた。
break # ループを抜ける。
i += 2
# 判定結果を出力する。
if flag == 0:
print(num,'は素数です。')
else:
print(num,'は素数ではありません。')
[実行例]
$ ./prime-number2.py 数字を入力してください。: 11 11 は素数です。 $ ./prime-number2.py 数字を入力してください。: 12 12 は素数ではありません。
コメント