#include <stdio.h>
#include <vector>

std::vector<int> primaries;

void fill_primaries(int max)
{
	primaries.clear();
	primaries.push_back(2);
	for(int i = 3; i <= max; i += 2) {
		int* k = &primaries[0];
		for(int j = primaries.size(); j > 0 && i % *k != 0; j--,k++) {
			if(*k * *k > i) {
				primaries.push_back(i);
				break;
			}
		}
	}
}

void  main(){
	fill_primaries(31623);
	for(int j = 0; j < primaries.size(); j++) printf("%d ", primaries[j]);
}

#include <stdio.h>
#include <vector>

// следующее простое после x
int next_prime(int x)
{
	static std::vector<int> cache;
	static int max_prime = 0;
	if(max_prime == 0) {
		cache.push_back(2);
		cache.push_back(3);
		max_prime = 3;
	}
	if(x >= max_prime) { // нет в кэше
		for(int i = max_prime + 2; x >= max_prime; i += 2) {
			int* k = &cache[0];
			for(int j = cache.size(); j > 0 && i % *k != 0; j--,k++) {
				if(*k * *k > i) {
					cache.push_back(i);
					max_prime = i;
					break;
				}
			}
		}
		return max_prime;
	} else if(x < 2) {
		return 2;
	} else { // поиск в кэше
		int* min = &cache[0];
		int* max = &cache[cache.size() - 1];
		while(max - min > 1) {
			int* mid = min + (max - min) / 2;
			if (*mid > x) {
				max = mid;
			} else {
				min = mid;
			}
		}
		return *max;
	}
}

void  main(){
	int x = 0;
	for(int i = 0; i <100; i++) {
		x = next_prime(x);
		printf("%d ", x);
	}
	printf("%d\n", next_prime(-3));
}