Напомним, что простыми числами называют такие числа, которые не имеют делителей, кроме 1 и самого себя. Так, простыми числами являются: \(2,3,5,7,11...\) Все остальные числа можно представить в виде произведения простых чисел: \(24 = 2 * 2 * 2 * 3\).

Решето Эратосфена - алгоритм, позволяющий найти все простые числа от 1 до \(N\) за \(O(n \log \log n)\). Данный метод (просеивания) впервые был предложен Эратосфеном Киренским в III веке до нашей эры.

Сам алгоритм достаточно тривиален: будем перебирать числа по возрастанию, начиная с 2, зачёркивая все числа, кратные текущему. Например, при обработке числа 2 будут зачёркнуты числа 4,6,8,…. Если мы обнаружили незачёркнутое число, это значит, что оно простое.

Работу решета можно значительно ускорить, если начинать зачёркивать числа, кратные \(p\), не с \(2p\), а с \(p^2\). Ведь числа \(2p,3p,5p,…\) уже были зачёркнуты при обработке чисел \(2,3,5,…\).

const int n = 100;
vector <int> resheto;
vector <int> primes;
for (int i = 0; i < n + 1; i++)
	resheto.push_back(i);//заполняем решето
for (int i = 2; i < n + 1; i++)
{
	if (resheto[i] != 0)
	{
		primes.push_back(resheto[i]);
		for (int j = i * i; j < n +1; j += i)
			resheto[j] = 0;//кратные i обнуляем
	}
}
for (int i : primes)
	cout << i << " ";

Пусть n - это наше ограничение по поиску простых чисел, мы объявляем его заранее как константу. Также мы создаем 2 вектора - resheto, собственно где мы храним решето, и primes, куда мы будем заносить простые числа. Далее начинаем обход решета - если текущее значение отлично от 0, то число простое, и мы заносим его в primes.