Sign in to follow this  
EmrldDrgn

Sieve of Sundaram

Recommended Posts

I've recently become interested in prime number sieves. The Sieve of Eratosthenes is simple, but I'm having quite a hard time understanding some of the other ones, especially the Sieve of Sundaram. Does anyone have/know of any example code for the algorithm, to help me understand how it works? I'd prefer Java or C++ if possible - all I've found so far has been Python, and I don't speak Python.

Share this post


Link to post
Share on other sites
I read beginning of the Wikipedia page, and it seems pretty straight forward:
include <iostream>
#include <vector>

int const N = 100; // Generate the primes up to 2*N

int main() {
std::vector<bool> l(N,true);
for (int j=1;;++j) {
int k=1+3*j;
if (k>=N)
break;
do {
l[k] = false;
k += 2*j+1;
} while (k<N);
}

for (int i=1; i<N; ++i) {
if (l[i])
std::cout << (2*i+1) << '\n';
}
}



Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this