[Algorithm] Sieve elements – Prime number Sieve

December 8, 2014 nguyenvanquan7826 Algorithm 2 responses
Sieve element algorithm is given by Eratosthenes to find prime. It is distinguished from other algorithms that examine the prime-style screening, Review all of the required test, the number that is not a prime number, then leave. Appropriate algorithm for the problem of finding all the prime numbers between [the, b] which is particularly effective when the distance between a, b is very large.

To find the number of primes not just based on the number of initial elements, Examples of 2 is prime, then the number is divisible by 2 certainly not a prime number, number 3 is prime, then all numbers are multiples of 3 disqualified, so on the number of retained as the prime.

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 [the, 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;
}