2 курс. Программирование на C++. Турнир 1, осень 2021

вход курсы / турниры задачи участники консоль модули компиляторы ключевые слова результаты

ru en cn

5458401

Пользователь

Акуленко Валерий Васильевич

Время

15:45<< 08.10.2021 15:47 (23 д. 06:20)

Обработка

15:47 ... 15:47 (6,75 сек.)

Файл

5458401.cpp (CLang++ 5.0.0 + Address Sanitizer)

Турнир

2 курс. Программирование на C++. Турнир 1, осень 2021

Задача

D: PrimeNumberGenerator

Набор тестов

Ограничения

Время: 1с Память: 512Мб

Состояние [?]

Принято

код | результаты

[печатать | | ]

≡

#ifndef LABS_CPP_PERSON_H
#define LABS_CPP_PERSON_H
#include <vector>
#include <cstdint>
#include <algorithm>
class PrimeNumberGenerator {
 public:
  explicit PrimeNumberGenerator(int start) : _tableInternalIndex(start) {
    while (_size < static_cast<size_t>(start))
    _size *= 2;
    _primeTable = std::vector<int64_t>(_size);
    CalcPrimes(start);
  }

int GetNextPrime() {
    std::vector<int64_t>::iterator it{};
    int64_t answ{};
    if (!_primeNumbers.empty()) {
      it = std::find(std::begin(_primeNumbers),
        std::end(_primeNumbers), _primeNumbers.front());
  }

if (it == std::end(_primeNumbers)) {
      _size *= 2;
      CalcPrimes(_size / 2);
    }
    answ = *it;
    _primeNumbers.erase(it);
    return answ;
  }

private:
  void CalcPrimes(int start) {
    for (size_t i = 0; i < _size; ++i) {
      _primeTable[i] = i;
    }

_primeTable[1] = 0;
    for (size_t i = 2; i < _size; ++i) {
      if (_primeTable[i] != 0) {
      for (size_t j = i * i; j < _size; j += i)
        _primeTable[j] = 0;
    }
    }
    int i = 0;
    while (_primeTable[i] < start) {
      _primeTable[i] = 0;
      i++;
    }
    FetchFromTable();
  }

void FetchFromTable() {
     for (auto x : _primeTable)
       if (x != 0)
      _primeNumbers.push_back(x);
    }
  size_t _size = 1500000;
  int _tableInternalIndex = 0;
  std::vector<int64_t> _primeTable;
  std::vector<int64_t> _primeNumbers;
};
#endif

(1 493 b)

0.118s 0.008s 9