[算法] 筛元素 – 素数筛

十二月 8, 2014 nguyenvanquan7826 算法 2 回复
筛分子算法由埃拉托色尼给出找到 灌注. 它是从研究的主要风格的检查其他算法区别, 检查所有必需的测试, 这不是一个素数的数量，然后离开. 合适的算法查找之间的所有素数的问题 [该, B] 这是特别有效的，当一个之间的距离, B是非常大的.

找到的素数的数量不仅基于初始元素的数量, 示例 2 是素数，则该数字是整除 2 当然不是素数, 号码 3 是素数，则所有的数字的倍数 3 被取消资格, 等的保留为素数.

素数筛是一种算法，埃拉托色尼的发现 素数. 它检查素数的基础过滤器. 在所有的数字我们要检查, 并取出假数. 适当找到所有质数 [该, B] a和b之间的距离远.

找一些不是素数, 只有基本素数以前. 例如 2 是一个素数, 因此所有的数字格 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;
}