Advertisement
carlos1993

Sieve of Eratosthenes

Sep 4th, 2013
248
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.79 KB | None | 0 0
  1. #include<iostream>
  2. #include <stdlib.h>
  3.  
  4. using namespace std;
  5. void listPrimes(int x);
  6.  
  7. int main() {
  8.  
  9.     listPrimes(5000);
  10. }
  11.  
  12. void listPrimes(int x) {
  13.     bool *not_prime = new bool[x];
  14.     unsigned j = 0, i = 0;
  15.  
  16.     for (i = 0; i <= x; i++) {
  17.         if (i < 2) {
  18.             not_prime[i] = true;
  19.         } else if (i % 2 == 0 && i != 2) {
  20.             not_prime[i] = true;
  21.         }
  22.     }
  23.  
  24.     while (j <= x) {
  25.         for (i = j; i <= x; i++) {
  26.             if (!not_prime[i]) {
  27.                 j = i;
  28.                 break;
  29.             }
  30.         }
  31.         for (i = (j * 2); i <= x; i += j) {
  32.             not_prime[i] = true;
  33.         }
  34.         j++;
  35.     }
  36.  
  37.     for ( i = 0; i <= x; i++) {
  38.         if (!not_prime[i])
  39.             cout << i << ' ';
  40.     }
  41.  
  42.     return;
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement