素数を判定しよう。
まず素数とは。
素数（そすう、英: primeあるいはprime number）とは、2 以上の自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。1 より大きい自然数で素数でないものは合成数と呼ばれる。
1は素数ではないの？
1 を素数とする定義に変えても、もとの「素数」を「1 以外の素数」と呼び替えることで矛盾は生じないが、多くの素数に関する定理でこの修正が必要になる。例えば 6 の素因数分解は、（積の順序を除いても）
6 = 2 × 3 = 1 × 2 × 3 = 12 × 2 × 3 = …
と無数に与えられることになり、一意性は「1 を含む素数」については成り立たない[3]。同様に、エラトステネスの篩は 1 を素数とすると 1 の倍数（すなわち他のすべての数）を消去し、残った唯一の数 1 を出力するので機能しない[11]。さらに、1 以外の素数で成り立つ様々な性質がある（例えば、自然数とそれに対応するオイラーのφ関数や約数関数の値との関係など）[12][13][14]。20世紀初頭までに 1 は素数ではなく「単数」という特別な分類に属するという見方が一般的になった[3]。
素数は正の約数が1と自分自身のみということですが、その約数とは
"2" であれば"1"と"2"、"3"であれば"1"と"3"のみ約数があるのでこの2つの数字は素数。"4"では"1"と"2"と"4"が約数となるので3つの約数を持つので素数ではありません。
素数であるかないかは１と自分以外の約数を持たない、もし他の約数がある場合は素数ではないということになります。
素数判定ですが、2は素数ですが偶数は素数ではないので
Swift
var isPrime = 8
if isPrime == 2{
print("素数です")
}else if isPrime%2 == 0{
print("素数ではありません")
}else{
print("素数の可能性があります")
}Python
isPrime =8
if isPrime == 2:
print("素数")
elif isPrime%2 == 0:
print("素数ではない")
else:
print("素数の可能性がある")
"8"を判定してみれば素数ではないと出ます。
奇数であっても素数とは限らないのでその判定も追加します。
素数を判定する数字を2から順番に割っていき割れたら終了するようにしています。
Swift
var isPrime = 11
var prime = false
if isPrime == 2{
print("素数です")
}else{
for i in 2..<isPrime{
if isPrime%i==0{
prime = false
break
}else{
prime = true
}
}
}
print(prime)出力は素数であれば"true"となります。
Python
isPrime = 17
prime = False
if isPrime == 2:
print("素数です")
else:
for i in range(2,isPrime):
if isPrime%i==0:
prime = False
break
else:
prime = True
print(prime)出力は素数であれば"True"となります。
C言語
#include <stdio.h>
#include <stdbool.h>
void subfunc(void);
int main() {
int isPrime = 5;
bool prime = false;
int i;
if (isPrime == 2){
printf("素数");
}else{
for (i = 2; i < isPrime; i++) {
if (isPrime%i==0){
prime = false;
break;
}else{
prime = true;
}
}
}
printf("%d\n",prime);
}C言語ではtrue,falseを使う場合は
#include <stdbool.h>
をインクルードする必要があります。
bool prime = false;
int i;
真偽値のデータ型は"bool"とします。for文の変数"i"についても宣言しておく必要があります。
実行するとtrueであれば"1"、falseであれば"0"と出力されます。
参考になるサイト
この記事が気に入ったらサポートをしてみませんか？