ある数が素数か素数以外かを判定するプログラムです。（C#、Java、C++対応）
CodeIQなどのプログラミングコンテストで問題としてよく出てくるので作ってみました。
最速の素数判定プログラム
C# 版
public static bool IsPrime(int num)
{
if (num < 2) return false;
else if (num == 2) return true;
else if (num % 2 == 0) return false; // 偶数はあらかじめ除く
double sqrtNum = Math.Sqrt(num);
for (int i = 3; i <= sqrtNum; i += 2)
{
if (num % i == 0)
{
// 素数ではない
return false;
}
}
// 素数である
return true;
}
なるべくなら自分が理解できる範囲のコードにしておきたいなぁというのがあるので、今はこれを最速版としています。（簡単でしょ？）
でも、問題を解くだけならこれぐらいの速さで十分な気がします。
これで不十分な場面が出てきたらまた考えましょう。
「ええぃサービスだ、JavaとC++の実装も持っていきやがれ！」（ほぼ同じ）
Java 版
public static boolean isPrime(int num) {
if (num < 2) return false;
else if (num == 2) return true;
else if (num % 2 == 0) return false; // 偶数はあらかじめ除く
double sqrtNum = Math.sqrt(num);
for (int i = 3; i <= sqrtNum; i += 2)
{
if (num % i == 0)
{
// 素数ではない
return false;
}
}
// 素数である
return true;
}
C++ 版
#include <math.h>
bool IsPrime(int num)
{
if (num < 2) return false;
else if (num == 2) return true;
else if (num % 2 == 0) return false; // 偶数はあらかじめ除く
double sqrtNum = sqrt(num);
for (int i = 3; i <= sqrtNum; i += 2)
{
if (num % i == 0)
{
// 素数ではない
return false;
}
}
// 素数である
return true;
}
Java版動かしてないけどたぶん大丈夫だと思います。。
数学用語の説明
私が分からなかった用語をざっくり説明します。
- 素数とは？ → 1と自分自身以外の数で割り切れない自然数のこと
- 合成数とは？→ 素数以外の数のこと
最速アルゴリズムの説明
実装してるアルゴリズムは主にこちらのサイトの内容を参考にしました。
素数判定 | アルゴリズムとデータ構造 | Aizu Online Judge
このサイトに、
素数判定では、「合成数xはp≦√xを満たす素因子pをもつ」という性質を利用することができます。
という記載がありますが、
「合成数xはp≦√xを満たす素因子pをもつ」＝「xが合成数ならば、√x以下の約数を持つ」
と言い換えることが出来ますので、ループの終了条件がMath.Sqrt(num)までになっている訳です。
単純にnumまで剰余演算をするのに比べると、ループ回数が減って処理速度が大幅に短縮されます。
その他のアルゴリズム
素数判定アルゴリズムは大きく分けて２種類があるようです。
- 決定的素数判定法
- 確率的素数判定法
決定的判定法とは、確実に誤りが出ない方法で素数判定を行うというもの。
確率的判定法とは、たまに誤りが出るかもしれないけど判定速度が劇的に速くなる方法。
決定的素数判定法の代表格は、「AKS素数判定法」
確率的素数判定法の代表格は、「ミラーラビン素数判定法(Miller-Rabin primality test)」
より速い実装が必要な人はこちらも検討してみてください。
おまけ
大多数の方は、上記の最速アルゴリズムが分かればこんなページに用は無いと思います。
最速アルゴリズムに至るまでの実装の過程を見たいという方のみ以降をお読み下さい。
単純な実装
割る数を1ずつ増やしていきながら、実際に割り切れるか確認する力技。
この方法は自分でも思いつきましたが、処理速度が遅すぎました。
private static bool IsPrime(int num)
{
if (num < 2) return false;
for (int i = 2; i < num; i++)
{
if (num % i == 0)
{
// 素数ではない
return false;
}
}
// 素数である
return true;
}
単純な実装を少し改良したもの
単純な実装に少し工夫をするだけで、処理速度が半分ほどになります。
簡単に言うと、偶数は2で割り切れるのが分かりきっているので、あらかじめ除きましょうということです。
同様に3の倍数、5の倍数をあらかじめ除くこともできる様ですが、それ程劇的には速くならないようです。
private static bool IsPrime(int num)
{
if (num < 2) return false;
else if (num == 2) return true;
else if (num % 2 == 0) return false; // 偶数はあらかじめ除く
for (int i = 3; i < num; i+=2)
{
if (num % i == 0)
{
// 素数ではない
return false;
}
}
// 素数である
return true;
}