Advertisement
DMG

Eratosthenes sieve

DMG
Oct 25th, 2014
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.76 KB | None | 0 0
  1. // http://www.algolist.net/Algorithms/Number_theoretic/Sieve_of_Eratosthenes
  2. // Eratosthenes Sieve (Prime numbers)
  3. void runEratosthenesSieve(int upperBound) {
  4.       int upperBoundSquareRoot = (int)sqrt((double)upperBound);
  5.       bool *isComposite = new bool[upperBound + 1];
  6.       memset(isComposite, 0, sizeof(bool) * (upperBound + 1));
  7.       for (int m = 2; m <= upperBoundSquareRoot; m++) {
  8.             if (!isComposite[m]) {
  9.                   cout << m << " ";
  10.                   for (int k = m * m; k <= upperBound; k += m)
  11.                         isComposite[k] = true;
  12.             }
  13.       }
  14.       for (int m = upperBoundSquareRoot; m <= upperBound; m++)
  15.             if (!isComposite[m])
  16.                   cout << m << " ";
  17.       delete [] isComposite;
  18. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement