#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;
}