smatskevich

Sieve

Sep 23rd, 2017
182
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Выводит все простые числа в диапазоне [1, n].
  2.  
  3. #include <assert.h>
  4. #include <iostream>
  5. using std::cin;
  6. using std::cout;
  7.  
  8. // Обертка массива целых чисел.
  9. struct CSimpleIntArray {
  10.     int* Data = 0;
  11.     int Size = 0;
  12.  
  13.     CSimpleIntArray() = default;
  14.     explicit CSimpleIntArray( int size ) : Data( new int[size] ), Size( size ) {}
  15.     CSimpleIntArray( const CSimpleIntArray& other ) = delete;
  16.     CSimpleIntArray( CSimpleIntArray&& other );
  17.     ~CSimpleIntArray() { delete[] Data; }
  18. };
  19.  
  20. inline CSimpleIntArray::CSimpleIntArray( CSimpleIntArray&& other ) :
  21.     Data( other.Data ),
  22.     Size( other.Size )
  23. {
  24.     other.Data = 0;
  25.     other.Size = 0;
  26. }
  27.  
  28. // ------------------------------------------------------------------------------------------------
  29.  
  30. CSimpleIntArray GetPrimes( int n )
  31. {
  32.     assert( n >= 1 );
  33.     int primesCount = 0;
  34.  
  35.     // Выделяем массив под решето Эратосфена.
  36.     bool* sieve = new bool[n + 1];
  37.     sieve[0] = false;
  38.     sieve[1] = false;
  39.     for( int i = 2; i <= n; ++i ) {
  40.         sieve[i] = true;
  41.     }
  42.  
  43.     // Выкалываем составные числа.
  44.     int currentPrime = 2;
  45.     while( currentPrime <= n ) {
  46.         ++primesCount;
  47.         // Выкалываем числа, кратные currentPrime.
  48.         for( int k = 2; k * currentPrime <= n; ++k ) {
  49.             sieve[k * currentPrime] = false;
  50.         }
  51.         // Двигаем currentPrime на следующее простое число.
  52.         for( ++currentPrime; currentPrime <= n && sieve[currentPrime] == false; ++currentPrime ) {}
  53.     }
  54.  
  55.     // Создадим и запомним массив чисел.
  56.     CSimpleIntArray primes( primesCount );
  57.  
  58.     int currentIndex = 0;
  59.     for( int i = 0; i <= n; ++i ) {
  60.         if( sieve[i] == true ) {
  61.             assert( currentIndex < primesCount );
  62.             primes.Data[currentIndex++] = i;
  63.         }
  64.     }
  65.  
  66.     delete[] sieve;
  67.     return primes;
  68. }
  69.  
  70. int main()
  71. {
  72.     int n = 0;
  73.     cin >> n;
  74.  
  75.     CSimpleIntArray primes = GetPrimes( n );
  76.  
  77.     for( int i = 0; i < primes.Size; ++i ) {
  78.         cout << primes.Data[i] << " ";
  79.     }
  80.  
  81.     return 0;
  82. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×