[Thuật toán] Sàng nguyên tố – Prime number Sieve

Tháng Mười Hai 8, 2014 nguyenvanquan7826 Thuật toán 2 responses
Sàng nguyên tố là thuật toán do Eratosthenes đưa ra để tìm các số nguyên tố. Nó có đặc điểm khác với thuật toán khác là kiểm tra các số nguyên tố theo kiểu sàng lọc, xét tất cả những số cần kiểm, những số nào không phải là số nguyên tố thì bỏ đi. Thuật toán thích hợp cho bài toán tìm tất cả các số nguyên tố trong khoảng [a, b] mà đặc biệt hiệu quả khi khoảng cách giữa a, b là rất lớn.

Để tìm các số không phải số nguyên tố chỉ cần dựa vào các số nguyên tố ban đầu, VD số 2 là số nguyên tố thì các số chia hết cho 2 chắc chắn không phải là số nguyên tố, số 3 là số nguyên tố thì tất cả các số là bội của 3 đều bị loại bỏ, cứ như vậy những số được giữ lại là các số nguyên tố.

Prime number Sieve is a algorithm of Eratosthenes to find prime number. It check prime number base filters. In all number we want check, and remove numbers false. It appropriate to find all prime number in [a, b] and the distance between a and b is far.

To find number not prime, only base prime numbers previous. E.g 2 is a prime number, so all number div 2 = 0 is false, 3 is a prime number and all number is multiplier of 3 is false,… Last, numbers remain is prime number we want.

Prime number Sieve
Prime number Sieve
#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;
}