#include <iostream>
#include <vector>
#include <cmath>

class PrimeNumberGenerator {
 private:
    std::vector<int> primeNumbers;
    int lastNumber;

 public:
    explicit PrimeNumberGenerator(int start) {
        if (start <= 2) {
            lastNumber = 2;
        } else {
            for (int i = 3; i < start; i += 2) {
                bool isPrime = true;
                for (unsigned int j = 0; j < primeNumbers.size(); ++j) {
                    if (i % primeNumbers[j] == 0) {
                        isPrime = false;
                        break;
                    }
                    if (primeNumbers[j] > sqrt(i)) break;
                }
                if (isPrime)
                    primeNumbers.push_back(i);
            }
            if (start % 2 == 0) {
                lastNumber = start + 1;
            } else {
                lastNumber = start;
            }
        }
    }

    int GetNextPrime() {
        if (lastNumber == 2) {
            lastNumber = 3;
            return 2;
        }
        for (int i = lastNumber; ; i += 2) {
            bool isPrime = true;
            for (unsigned int j = 0; j < primeNumbers.size(); ++j) {
                if (i % primeNumbers[j] == 0) {
                    isPrime = false;
                    break;
                }
                if (primeNumbers[j] > sqrt(i)) break;
            }
            if (isPrime) {
                primeNumbers.push_back(i);
                lastNumber = i;
                break;
            }
        }
        lastNumber += 2;
        return lastNumber - 2;
    }
};

int main() {
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	
	PrimeNumberGenerator test(491);
    for (int i = 0; i < 5; ++i) {
        std::cout << test.GetNextPrime() << std::endl;
    }

    return 0;
}