素数判定のアルゴリズムをC#で書いた
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
- 出版社/メーカー: マイナビ
- 発売日: 2015/01/30
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (7件) を見る
螺旋本 18.1 素数判定より、理解したことと書いたコードを載せる。
「ぐぬぬ...」をたくさん繰り返したが、その都度考えて「あーそうかそういうことか！」ってなって楽しかった。
素数 is 何
「自分自身と1以外で割り切れない自然数のこと」を素数（Prime Number）という。
当たり前じゃんと思う方も要るかもしれないが、この定義を「自分自身と1以外で割り切れない」と「自然数」の2つに分解して考えてみる。
文系卒なのでどうかお手柔らかに。
①「自分自身と1以外で割り切れない」とは。
ここで言う「数」とは自然数を指す（②で後述）
たとえば、5は素数であるが、これは5という数は5自身と1以外で割り切れないため。
そして、ある数を「割り切れる数」のことを約数という。
また、約数(Common Number)が「自分自身」と「1」の2つであるとき、それを素数という。
例を上げる。
3は素数。なぜなら、3は1と3でしか割り切れず、約数が2つであるから。
対して、4は素数ではない。なぜなら、4は1と2と4で割り切れ、約数が3つであるから。
また、1は約数ではない。なぜなら、1は1でしか割り切れず、約数が一つであるから。
②「自然数」とは。
自然数(Natural Number)とは何か。
自然数については以下のマインドマップに整理した。このほうがわかりやすいとおもわれる。
実数 所有者： okitsune concon
要するに自然数は正の整数で、例えば「1,2,3,4,5....」を指す。
まとめると、
「自分自身と1以外で割り切れない自然数のこと」を素数（Prime Number）
これは換言すると、
①割り切れる数(約数)が「自分自身」と「1」の2つであり、② 1を除く正の整数 が素数である。
さて、この理解をもとに、素数かどうかを判定するコードを作る。
素数判定の実装 その１
愚直に書いたら以下のようになる。
public static bool IsPrime(int x)
{
if (x <= 1) return false; // 1以下は素数ではない
//自分自身と1以外で割れるかどうか
int y = x - 1;
while(y > 1)
{
if (x % y == 0) return false;
y--;
}
return true;
}
これでも動くが、計算量がO(N)であり、遅い。
実際、Time Limit Exceededで処理時間が遅くて時間超過ですという判定を食らっている。
#3404197 Solution for ALDS1_1_C
改善の必要がある。
素数の実装 その２
ここで、「合成数xはp<=√xを満たす素因子pを持つ」という性質を利用して高速に処理できるようにする。
は？？？「合成数xはp<=√xを満たす素因子pを持つ」？？？
文系にわかるように話して？？？
となったので、腰を据えて考えた。
素因子とは「その数の約数であり、かつ、素数である」数を指す。
数学において、ある自然数の素因数（そいんすう、英: prime factor）とは、その約数になる素数のことである。ある数の素因数を求めてその積の形で表すことを素因数分解という。例えば 60 は 22×3×5 と素因数分解されるので 60 の相異なる素因数は 2, 3, 5 の3つである。
まとめると、
素因子とは「その数を割り切れる数であり、かつ、素数である」数を指す。つまり、「その数の約数であり、かつ、素数」のことをさす。
なので、「合成数xはp<=√xを満たす素因子pを持つ」という文言は、「素数でない数xはp<=√xを満たす、xの約数でありかつ素数であるpが存在する」ということを指す。
①割り切れる数(約数)が「自分自身」と「1」の2つであり、② 1を除く正の整数 **が素数である。
と上で述べたが、ここから「1を除く正の整数」という条件がわかるので、pの取りうる範囲は1 < p <= √x になる。
なので、
1 < p <= √x の範囲内で、割り切れる数が存在すれば、その数xは素数ではない。
1 < p <= √x の範囲内で、割り切れる数が存在しなければ、その数xは素数である。
ということになる。
例えば、
12が素数かどうか判定するときには、1 < p <= √12 (= 3.464...) の中の整数 2と3で12が割れるかどうかを調べればいい。
12はもちろんpで割り切れるので、これは素数ではない。
対して、
13が素数かどうか判定するときには、1 < p <= √13 (= 3.6055...) の中の整数 2と3で13が割れるかどうかを調べればいい。
13はpでは割り切れないので、13は素数である。
これをコードに載せる。
public static bool IsPrimeB(int x)
{
if (x <= 1) return false;
// Composite Number == not Prime Number
// xは 1 < i <= root(x) で割り切れるかだけを調べる
double r = Math.Sqrt(x);
for (int i = 2; i <= r; i++)
{
if (x % i == 0) return false;
}
return true;
}
計算量はO(√x)なので、O(N)よりも相当速くなる。なので、処理速度で怒られることがなくなった。
素数の実装 その３
その２まででも良いのだが、エラトステネスのふるいというアルゴリズムを使ってNまでの素数を列挙するアルゴリズムを実装する。
2からNまでの整数を列挙する。 最小値である、2を残して、2の倍数を削除する 残った最小値である、3を残して、3の倍数を削除する。 残った最小値である、5を残して、5の倍数を削除する。
...ということを繰り返すアルゴリズム。
public static void SieveOfEratosthenes(int n)
{
bool[] isPrime = new bool[n+1];
for (int i = 0; i < n; i++)
{
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i < Math.Sqrt(n); i++)
{
int j;
if (isPrime[i])
{
j = i + i;
while (j <= n)
{
isPrime[j] = false;
j = j + i;
}
}
}
for (int i = 0; i < isPrime.Length; i++)
{
if (isPrime[i])
{
WriteLine(i);
}
}
}
public class ALDS1_1_C
{
public static void Main(string[] args)
{
int N = int.Parse(ReadLine());
SieveOfEratosthenes(N);
}
}
// N = 120 120 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113
