おそらく、数学のプログラミングを学習するとき、すべてのプログラマが直面する問題の一つは、いくつかの材料をチェックしていることである必要があります プライム か否か.

その私たちの最初のアルゴリズム: 番号を確認することは、nの約数である可能性が高いです (要素を検討する必要性), に至るまで、これらの数字 2 nまで – 1. 次のようなアルゴリズムは、単にCにインストールされています:

int checkPrime(int n) {
	if (n < 2)
		return 0;
	int i;
	for (i = 2; i < n; i++)
		if (n % i == 0)
			return 0;
	return 1;
}

上の設定で, nが素数である場合、ループが実行されるまで、私= nの – 1 最終的な結論を出すことができるようにします. しかしながら, 我々はiの値をチェックする必要があります= nでないことが表示されますもう少し考えてみて – 1 これは本質的に単にN / 2 (n個のdiv 2) N / 2より大きいn個のない除数が存在しないため. 以下のようにアルゴリズムがあります:

int checkPrime(int n) {
	if (n < 2)
		return 0;
	int i;
	for (i = 2; i <= n / 2; i++)
		if (n % i == 0)
			return 0;
	return 1;
}

我々はまた、値をチェックする必要がないことがわかります背中を少し考えてみてN / 2にのみルートに必要 2 nがあります (あなたはなぜそんなに見て少し計算します ). 私たちは、新しいアルゴリズムを持っています: (注宣言ライブラリ math.h ベースを計算します)

#include <math.h>

int checkPrime(int n) {
	if (n < 2)
		return 0;
	int i;
	for (i = 2; i <= sqrt(n); i++)
		if (n % i == 0)
			return 0;
	return 1;
}

素数はちょうど数を除く奇数であるかもしれません 2, したがって、彼らは偶数で割り切れることはできませんので、我々は単に除数をチェックする必要があります (iの値) 奇数であります, ように、次のアルゴリズムは、以下の:

#include <math.h>
int checkPrime(int n) {
	int i;
	int m;
	if (n < 2)
		return 0;
	if (n == 2)
		return 1;
	if (n % 2 == 0)
		return 0;

	m = (int) sqrt(n);
	for (i = 3; i <= m; i += 2)
		if (n % i == 0)
			return 0;
	return 1;
}

明らかに以前のアルゴリズムに比べ, iの値が半分にチェックする必要があります. このようなアルゴリズムを加速し改善するための鍵は、制御変数iの値を変更する文であります, 私たちはそれがより効率的なアルゴリズムにつながる確認する必要があり、iの値を小さくする必要があります.
最近では、除数を考慮してiの値の半分を排除しました 2 可能なn個. 次に、我々はいくつかのかもしれn個の次の素因数を考慮してアルゴリズムを改善します 3. nが割り切れる場合 2 または 3 どこに締結することは容易です (もちろん、他の2つの値のn個の必須). 逆にN形1 + 6Iのおおよその数を有することになります,5+6で , 私は、私は=の値で開始します 5. 唯一の私は1 + 6Iの形でテスト候補を逃すことになる場合でも、私たちは、私は+ 2より多くの価値をチェックします (注意: 我々はI = 5で起動したときに、我々は、私は2を持っています+ <=> 1 + 6I) 十分なため. だから、新しいアルゴリズム (5) 以下のようになります:

#include <math.h>
int checkPrime(int n) {
	int i;
	int m;

	if (n < 2)
		return 0;

	if (n == 2 || n == 3)
		return 1;
	if (n % 2 == 0 || n % 3 == 0)
		return 0;
	
	m = (int) sqrt(n);
	for (i = 5; i <= m; i = i + 6)
		if (n % i == 0 || n % (i + 2) == 0)
			return 0;
	return 1;
}

素数は、技術的なアルゴリズムを使用することによっても向上させることができるが繰り返される問題を検討するには ふるい要素 ここで.

単純なアルゴリズムのプレゼンテーションを通じて、小さな素数をチェックします, 私は小さな内プログラミングコンテストや問題に使用されることをあなたに良いアルゴリズムを与える願っています, それによって設定アルゴリズムを微調整示します. 異なる設定を持つことができますが、同じアルゴリズム, 効果は異なります, より効果的な、それが詳細に基づいてされたときには非常にささいなように見えました, 注目すべきではありません.

何か良いアルゴリズムが存在する場合, がある, 私たちは共有の議論に成果を見ています, 詳細はこちら.

原著 / ソース: vietsource.net