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

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

ru en cn

5479008

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

Павлюк Роман Сергеевич

Время

12:26<< 13.10.2021 12:29 (28 д. 03:03)

Обработка

12:29 ... 12:29 (5,49 сек.)

Файл

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

Турнир

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

Задача

D: PrimeNumberGenerator

Набор тестов

Ограничения

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

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

Принято

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

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

≡

#pragma once

#include <vector>

class PrimeNumberGenerator {
 public:
    explicit PrimeNumberGenerator(int start) : start(start <= 1 ? 2 : start) {}

int GetNextPrime() {
        int end = this->start * 2 + 1;
        bool *matrix = new bool[end];
        for (int i = 2; i < end; ++i) {
            matrix[i] = false;
        }
        int p = 1;
        while (true) {
            for (int i = p + 1; i < end; ++i) {
                if (!matrix[i]) {
                    p = i;
                    break;
                }
            }
            if (p * p > end - 1) {
                break;
            }
            int i = p;
            while (i * p < end) {
                matrix[i * p] = true;
                i++;
            }
        }
        for (int i = this->start; i < end; ++i) {
            if (!matrix[i]) {
                this->start = i + 1;
                delete[] matrix;
                return i;
            }
        }
        delete[] matrix;
        return this->start;
    }

private:
    int start;
};

(1 090 b)

0.058s 0.012s 9