Euler’s Sieve: Prime numbers generator

Here’s a very simple algorithm that generates a list of all random numbers up to “n.” You just pass it an bool array of size “n+1” and “n” itself. The algorithm marks elements with prime indices in the array as true, and sets the rest to false.

void euler_sieve(int n, bool *a) {
	// Initialize the array
        a[0] = false;
        a[1] = false;
	for (int i = 2; i <= n; i++) {
		a[i] = true;
	}
	
	for (int i = 2; i <= n/2; i++) {
		/* If the current elements is prime, 
		 * mark all its multiples as not prime
		 */
		if (a[i]) { 
			for (int j = i + i; j <= n; j += i) {
				a[j] = false;
			}
		}
	}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s