皆さんこんにちは、大きい数の場合、素数を見分けるのって難しいですよね。そんな時、僕が素数の判定に試している方法を話していきます。
まずは最も簡単な、見れば一瞬で分かる場合についてです。
1の位が2の倍数の場合:
例えば、32,40,52,178,1348などです。
これらの場合必ず2で割ることができます。つまりその数は素数です。
次に、１の位が５の倍数の場合:
例えば、15,50,120,2305などです。
これも必ず5で割ることができます。同様に素数になります。
次は少し難易度が上がりますが、数秒かければ判定できます。
３の倍数の判定:
３の倍数の判定は整数の全ての桁の数の和が、３で割れればその数は3倍数と判断できます。例えば、12,24,123,273,1113など
判断の仕方としては、1113の場合1+1+1+3=6
6は3で割ることができるので1113は3で割ることができます。
よって素数です。
難易度がまた上がりますが、その数より大きく、近い平方数を見つける方法です。
例えば、253という数は素数か判定したい場合、253よりも大きい最も数値が近い平方数であるが見つかります。16×16＝256なので、253は15以下の素数で大きい数から割っていくと、最初の13では割り切れない、次に11で割ると
つまり、253は素数ではないと判定できます。
他にもフェルマーの小定理という素数判定法があるので興味がある人は調べてみてください。(小高)
