素数を計算してみる

2022年12月21日

C#を使って素数を計算してみましょう
学習用なので、どのように考えていくのかを順を追って説明しています
初学の方ではある程度理解できるのではないでしょうか

定義

2 以上の自然数で、正の約数が 1 と自分自身のみ

考え方

解法にはいろいろありますが、今回は単純に上記の定義をて計算するようにコーディングしたみましょう
手計算の高速バージョンと考えればいいですね

繰り返し

２から10までの間の素数を計算する場合、次のようにfor文を使うことになります

for (int i = 2; i <= 10; i++)
{
    // ２から10まで繰り返される処理
}

約数の計算

%を使うと割り算の余りが計算できます
例えば、４割る２は２余り０ですよね
次のif文は余りが０かを判定しています
この場合、0なのでブロックの処理に進みます

if (4 % 2 == 0)
{
    // 割り切れた
}

偶数を表示してみる

上記を組み合わせると次のように偶数が表示されます

for (int i = 2; i <= 10; i++)
{
    if (i % 2 == 0)
    {
        Console.WriteLine(i);
    }
}

結果

特定の数値が素数かを判定する

上記を応用すると次のコードが考え出されます
特定（今回は10）を２、３、４と順番に割っていき、余りが０になるパターンがあったら、それは素数ではありませんね
素数ではないと判定された場合、即座にbreak文にようり、forループを抜けるようになっています
なぜなら、もう素数ではないことがわかっているので、最後まで判定することが無意味だからです

int number = 10;

for (int i = 2; i < number; i++)
{
    if (number % i == 0)
    {
        Console.WriteLine("素数ではない");
        break;
    }
}

結果（number = 10）

結果（number = 11）

ただし、このコードでは素数であるときに「素数である」と表示したくてもできない欠点があります
なぜなら、素数の時も素数でない時もfor文を抜けてくるところが一緒だからです

int number = 10;

for (int i = 2; i < number; i++)
{
    if (number % i == 0)
    {
        Console.WriteLine("素数ではない");
        break;
    }
}
// 素数でもそうでなくてもこれ以降のコードが実行されます

コードの更新

次のように素数ではない場合、check変数がtrueになる情報を追加して実行すると、両方のメッセージを表示することができます

int number = 11;

bool check = false;

for (int i = 2; i < number; i++)
{
    if (number % i == 0)
    {
        check = true;
        break;
    }
}

if (check)
{
    Console.WriteLine("素数ではない");
}
else
{
    Console.WriteLine("素数です");
}

結果（number = 10）

結果（number = 11）

１から10までを１つずつチェックしていく

これまではnumberが10に固定でしたが、これをループすることで実現してみましょう

for (int number = 2; number <= 10; i++)
{
    // numberが素数かチェックするコード
}

コードをブロック内にコピーすると次のようになります
繰り返しになりますので、素数でない場合（checkがtrueになっている）では、初期のfalseに戻しておきます

bool check = false;

for (int number = 2; number <= 10; number++)
{
    for (int i = 2; i < number; i++)
    {
        if (number % i == 0)
        {
            check = true;
            break;
        }
    }

    if (check)
    {
        check = false;
        Console.WriteLine($"{number}は素数ではない");
    }
    else
    {
        Console.WriteLine($"{number}は素数です");
    }
}

結果

素数だけシンプルに表示したい場合、次のようなコードにすることもできます

bool check = false;

for (int number = 2; number <= 10; number++)
{
    for (int i = 2; i < number; i++)
    {
        if (number % i == 0)
        {
            check = true;
            break;
        }
    }

    if (!check)
    {
        Console.Write($"{number},");
        continue;
    }
    check = false;

}

結果

計算量を減らす

素数に、偶数が存在しない（つまり２で割り切れた時点で素数でない）ので、2飛ばしで割っていけばいいでしょう
割る数を３から始めて、5,7,9・・・と変更していけばいいですね
%演算を使うのではなく、for文を次のように変更して実現します

for (int number = 3; number <= 10; number += 2)

３から始めますので、素数である２は最初に表示しておくといいでしょう

Console.Write("2,");

完成したコード

まとめると次のようになります
今回は、100までの素数を計算してみました

bool check = false;

Console.Write("2,");

for (int number = 3; number <= 100; number += 2)
{
    for (int i = 3; i < number; i++)
    {
        if (number % i == 0)
        {
            check = true;
            break;
        }
    }

    if (!check)
    {
        Console.Write($"{number},");
        continue;
    }
    check = false;

}

結果

おまけ

ListやLINQを使うと次のようなコードにもできます
・・・ただし、計算速度が速いわけではありません

// 3,5,7,9...といった奇数リストの作成
var numbers = Enumerable.Range(3, 100 - 3).Where(n => n % 2 != 0).ToList();
// 合成数（素数以外）をListとして保管
var compositeNumbers = new List<int>();

foreach (var number in numbers)
{
    for (int i = 3; i < number; i++)
    {
        if (number % i == 0)
        {
            compositeNumbers.Add(number);
            break;
        }
    }
}

// 用意した奇数リストから合成数（素数でない数）を除く
numbers.RemoveAll(compositeNumbers.Contains);
// ２お頭に追加しておく
numbers.Insert(0, 2);

// 一覧の表示
foreach (var primeNumber in numbers)
{
    Console.Write($"{primeNumber},");
}