[アルゴリズム] ふるい要素 – 素数ふるい

12月 8, 2014 nguyenvanquan7826 アルゴリズム 2 回答
ふるい要素アルゴリズムは見つけることエラトステネスで与えられる プライム. これは、プライムスタイルのスクリーニングを調べる他のアルゴリズムとは区別される, 必要なテストをすべて確認, 素数でない数は、その後のままに. 間のすべての素数を見つける問題のために適切なアルゴリズム [ザ·, B] これは特に有効であるときとの間の距離, bが非常に大きい.

素数の数を確認するにはちょうど最初の要素の数に基づいていない, の例 2 、その後数が割り切れる素数です 2 確かではない素数, 数 3 素数である、すべての数字は、の倍数である 3 失格, そうプライムとして保持の数に.

素数ふるいを見つけるためにエラトステネスのアルゴリズムである 素数. これは、素数ベースのフィルタをチェック. すべての数では、チェックしたい, と偽の番号を削除. その中のすべての素数を見つけることが適切な [ザ·, B] aとbの間の距離が遠い.

数ではない素数を見つけるには, 前のベース素数のみ. E.g 2 素数, そのように、すべての数値のdiv 2 = 0 偽である, 3 素数であり、すべての数値は、乗数である 3 偽である,… ラスト, 数字は、私たちが望む素数で残る.

素数ふるい
素数ふるい
#include <stdio.h>

void primeLessN(int n) {
	n = n + 1; // array in C begin by 0, so I add 1 into n

	int prime[n];
	int j, num;
	prime[0] = prime[1] = 0;

	// all number div 2 = 0 is false
	for (num = 2; num < n; num++) {
		if (num > 2 && num % 2 == 0)
			prime[num] = 0;
		else
			prime[num] = 1;
	}

	// find prime number begin from 3
	num = 3;
	while (num <= n / 2) {
		// find and set false for multiplier of p
		for (j = num; num * j < n; j++)
			prime[num * j] = 0;

		// find next prime number
		do {
			num += 2;
		} while (!prime[num]);
	}

	// out all prime number smaller n
	for (num = 2; num < n; num++)
		if (prime[num])
			printf("%-3d", num);
}

int main() {
	primeLessN(97);

	//system ("pause");
	return 0;
}