smatskevich

PrimesWithRequests

Sep 24th, 2016
213
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Вывод простых чисел в диапазоне от 1 до n.
  2. #include <iostream>
  3. #include <assert.h>
  4. using std::cin;
  5. using std::cout;
  6.  
  7. // Массив целых чисел фиксированной длины.
  8. // При использовании необходимо гарантировать, что размер Body совпадает с Size.
  9. struct CArray {
  10.     int* Body;
  11.     int Size;
  12.  
  13.     CArray() : Body( 0 ), Size( 0 ) {}
  14.     ~CArray() { delete[] Body; }
  15. };
  16.  
  17. // Возвращает простые числа в диапазоне от 1 до n включительно.
  18. void GetPrimes( int n, CArray& primes )
  19. {
  20.     // Выделяем массив под решето.
  21.     bool* sieve = new bool[n + 1];
  22.     for( int i = 0; i <= n; ++i ) {
  23.         sieve[i] = true;
  24.     }
  25.     sieve[0] = sieve[1] = false;
  26.  
  27.     int primesCount = 0; // Количество простых.
  28.     for( int i = 2; i <= n; ++i ) {
  29.         if( sieve[i] ) {
  30.             // Выкалываем кратные.
  31.             for( int k = 2 * i; k <= n; k += i ) {
  32.                 sieve[k] = false;
  33.             }
  34.             ++primesCount;
  35.         }
  36.     }
  37.  
  38.     primes.Size = primesCount;
  39.     primes.Body = new int[primesCount];
  40.     int k = 0;
  41.     for( int i = 2; i <= n; ++i ) {
  42.         if( sieve[i] ) {
  43.             primes.Body[k++] = i;
  44.         }
  45.     }
  46.  
  47.     delete[] sieve;
  48. }
  49.  
  50. int main()
  51. {
  52.     int n = 0;
  53.     cin >> n;
  54.  
  55.     CArray primes;
  56.     GetPrimes( n, primes );
  57.  
  58.     int requestsCount = 0;
  59.     cin >> requestsCount;
  60.  
  61.     for( int i = 0; i < requestsCount; ++i ) {
  62.         int primeIndex = 0;
  63.         cin >> primeIndex;
  64.         assert( primeIndex < primes.Size );
  65.         cout << primes.Body[primeIndex] << std::endl;
  66.     }
  67.  
  68.     return 0;
  69. }
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.

×