試し割り

ホームアルゴリズム入門講座 > 試し割り

試し割り

素数とは?

素数とは「1と自分以外の数で割ることのできない数。ただし、1は除く」です。

素数をどのように暗号化に用いるかというと、以下のような特性を用います。

素数 p, q が十分に大きな値であるとき、
n = p * q
で n は簡単に求まるが、
n から p, q を求めることは非常に困難である

素数かどうかを判断する

素数は「1と自分以外で割ることのできない数」なのですから、実際に2から割っていってみればいいのです。そして、途中のどこかで割り切れたらそれは素数なのです。

このように全部わってみる素数判定法を「試し割り」と呼びます。

今回はこの「試し割り」を拡張して、「 n より小さい素数をすべて列挙するプログラム」を作ります。

ソースコード

using System;

namespace Prime1
{
	class MainClass
	{
		public static void Main(string[] args)
		{
			int n = 1000;
			int count = 0;
			bool frag;
			for(int i=2;i<n;i++)
			{
				frag = true;
				for(int y=2;y<i;y++)
				{
					count++;
					if (i % y == 0)
					{
						frag = false;
						break;
					}
				}
				if(frag) Console.WriteLine(i);
				
			}
			Console.WriteLine("{0} times repeat",count);
		}
	}
}

次回やる「エラトステネスのふるい」と比較するために、実行回数を計算しています。1000までの素数を求めるのに7万8千回くらい実行しました。エラトステネスのふるいはどうでしょうか。

解説

とくに解説の必要はないでしょう。まず「素数である」と仮定し、「素数でない」と分かった時点でループを抜けます。ループに最後まで残っていた場合は「素数である」という仮定が確定に変わります。

繰り返しを間違えて 1 から始めると、素数は存在しなくなってしまいますので注意してください。

だれでも気づくことですが、2や3や5は素数ですが、それらの倍数は素数ではありません。この特性を使って、次回やる「エラトステネスのふるい」を実装します。