Back to General and Gameplay Programming

Sieve of Sundaram

General and Gameplay Programming Programming

Started by EmrldDrgn February 24, 2010 06:01 PM

0 comments, last by alvaro 14 years, 1 month ago

EmrldDrgn

198

Author

February 24, 2010 06:01 PM

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.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~I program in C++, on MSVC++ '05 Express, and on Windows. Most of my programs are also for windows.

alvaro

21,604

February 24, 2010 10:13 PM

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*Nint 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)      std::cout << (2*i+1) << '\n';  }}