Решето Эратосфена

В этот статье мы сделаем экскурс в алгоритмы поиска простых чисел и рассмотрим один из алгоритмов, который реализует такой поиск. Этот метод поиска получил название "Решето Эратосфена", в честь древнегреческого математика Эратосфена Киренского. А "решето" потому, что мы как бы просеиваем массив чисел, оставляя в нем только простые числа.

Вспомним, что простым числом, является число, которое без остатка может делиться только само на себя, ну и, конечно же, на единицу. Из школьного курса вы, наверное, помните некоторые из простых чисел - это 5, 7, 11, 13, 17 и так далее. Давайте теперь рассмотрим сам принцип работы алгоритма поиска простых чисел. Этот метод поиска достаточно прост, поэтому, при желании, вам все станет очень скоро понятно.

Решето Эратосфена - алгоритм работы. Язык программирования С++

1. Для примера мы будем производить поиск простых чисел в интервале от 0 до 1000. Для этого нам нужно создать массив логических элементов размерностью 1000. Почему логических, поймете далее. Объявляем массив

const int size = 1000;
bool array[size];

2. Теперь нам нужно присвоить начальные значения элементам массива, т.к. на данный момент они содержат различный системный "мусор". Поступим так: присвоим всем элементам массива значения "true" - истина или единица. По мере работы алгоритма поиска простых чисел, все элементы массива (они у нас изначально установлены в true) с "простыми" индексами (заметьте, что здесь речь идет именно об индексах, т.к. наши искомые простые числа у нас будут выражаться в значениях индексов элементов массива) останутся быть равными "true", а все остальные установятся в "false" - ложь, или нуль. Т.е. теперь вы поняли, почему массив у нас содержит логические значения, а если и что-то не понятно, то, разобрав код, все встанет на свои места. Заполняем массив, начиная со второй ячейки, т.к. 0 и 1 не относят к простым, а значит и можно сразу их исключить

for(int k = 2; k < size; k++)
	array[k] = true;

3. А теперь самое важное: рассмотрим сам алгоритм поиска простых чисел, т.е. само решето Эратосфена

Для того чтобы просматривать массив и его индексы нам нужен цикл - делаем цикл (0 и 1 индексы мы не просматриваем). В этом цикле мы будем просматривать значения от 2 до значения корня из size. Почему так? Потому что, дойдя до корня из size, уже будут отсеяны все числа, не относящиеся простым. Поступая таким образом, мы уменьшаем количество итераций, а, соответственно, и нагрузку на процессор компьютера, что есть хорошо.

for(int i = 2; i < sqrt(size); i++)
{

}

Для "просева" на решете Эратосфена находится первый элемент массива с истинным значением. В самом начале работы программы этим элементом будет элемент с индексом 2. Далее выполняется условие if и мы попадаем на внутренний цикл for, который служит для просмотра остальной части массива (с 3 по 1000 индексы). Значение каждого индекса, а наши числа у нас выражены в индексах, будут проверяться на наличие остатка от деления на 2. Если число делится без остатка, значит, оно уже не может быть простым и значит, соответственно, выставляем эту ячейку в false. Смотрим код

for(int i = 2; i < sqrt(size); i++)
{
	if(array[i] == true)
	{
		for(int j = i * 2; j < size; j++)
		{
			if(j % i == 0)
				array[j] = false;
		}
	}
}

Для более наглядной демонстрации того, что произойдет после первой итерации, где i = 2 привожу рисунок для массива из 20 значений, по аналогии вы поймете, что происходит с нашим массивом из 1000 элементов.

Решето Эратосфена - алгоритм работы

Как видите, все элементы массива со значениями индексов, кратных двум "просеялись" и отметились как false. Это примерно половина значений всего нашего массива.

Переходим на следующую итерацию, в которой i = 3. Выполняется условие if, т.к. 3 не было "просеяно" в предыдущей итерации, попадаем опять же на внутренний цикл, который обрабатывает оставшуюся часть массива (индексы от 4 до 1000).

Рисунок ниже иллюстрирует полученную картину

Решето Эратосфена

Как видите, были исключены все числа, кратные трем, не исключенные ранее "двойкой".

Переходим к следующей итерации, где i = 4. Здесь условие if не выполняется, поэтому "просеиваться" ничего не будет. Далее, следующая итерация с i = 5, здесь будут помечены в false значения массива с индексами кратными 5, которые не были помечены ранее по иным критериям: исключаются 25, 35, 45 и так далее. Следующими "рабочими" итерациями, в которых будут выполняться "просевы" являются итерации с i = 7, 11, 13, 17 и так далее, вплоть до корня из size (т.к. после него уже не может встретиться число, не относящееся к простому).

4. Завершающим этапом работы алгоритма "Решето Эратосфена", является печать результатов. Для вывода результатов воспользуемся таким циклом

for(int i = 2; i < mySize; i++)
{
	if(myArray[i] == true)
		cout << i << endl;
}

5. Итог работы:

Алгоритм поиска простых чисел - решето Эратосфена на С++. Первый способ

//Алгоритм поиска простых чисел - Решето Эратосфена

#include <iostream>

//прототип функции
void printarray(bool[], const int);

using namespace std;

int main()
{
	const int size = 1000;
	bool array[size];

	for(int k = 2; k < size; k++)
		array[k] = true;

	for(int i = 2; i < sqrt(size); i++)
	{
		if(array[i] == true)
		{
			for(int j = i * 2; j < size; j++)
			{
				if(j % i == 0)
					array[j] = false;
			}
		}
	}

	printarray(array, size);

	return 0;
}

//функция для вывода результатов работы
void printarray(bool myArray[], const int mySize)
{
	int counter = 0;

	for(int i = 2; i < mySize; i++)
	{
		if(myArray[i] == true)
		{
			cout << i << endl;
			counter++;
		}
	}

	//выводим общее количество найденных простых чисел
	cout << endl << "Total: " << counter << endl;
}

Результат работы программы: (было найдено 168 простых чисел)

Решето Эратосфена - программа на С++

6. В пятом пункте был изложен первый способ реализации алгоритма поиска простых чисел. Предлагаю вашему вниманию и второй способ, в котором массив будет содержать не логические значения (истина / ложь), а значения целых чисел, которые мы будем "просеивать" на решете Эратосфена. Т.е. принцип работы алгоритма тот же, только реализация несколько иная. Возможно, вам эта реализация понравится даже более предыдущей, смотрим код

Алгоритм поиска простых чисел - решето Эратосфена на С++. Второй способ

//Решето Эратосфена

#include <iostream>

void simplePrint(int[], const int);

using namespace std;

int main()
{
	const int size = 100;
	int array[size];

	for(int k = 0; k < size; k++)
		array[k] = k;

	array[1] = 0;

	for(int i = 2; i < sqrt(size); i++)
	{
		if(array[i] != 0)
		{
			for(int j = i * 2; j < size; j += i)
			{
				array[j] = 0;
			}
		}
	}

	simplePrint(array, size);

	return 0;
}

void simplePrint(int array[], const int size)
{
	for(int i = 0; i < size; i++)
		if(array[i] != 0)
			cout << array[i] << endl;
}

В этой реализации мы также задаем массиву начальные значения, но уже не логические, а числовые (0, 1, 2, 3, 4, 5 ...). Эти числовые значения и будут теми числами, которые мы будем "просеивать" на решете Эратосфена. Задаем значения таким кодом

for(int k = 0; k < sqrt(size); k++)
	array[k] = k;

Числа, которые не будут являться простыми, мы будем помечать, как ноль. Мы знаем, что числа 0 и 1 не являются простыми числами, поэтому их сразу можно пометить в нули: первая ячейка массива итак нулевая, а вот вторую, содержащую единицу, нужно поменять

array[1] = 0;

Далее идет цикл обработки чисел

for(int i = 2; i < sqrt(size); i++)
{
	if(array[i] != 0)
	{
		for(int j = i * 2; j < size; j += i)
		{
			array[j] = 0;
		}
	}
}

Разберем первую итерацию: i = 2. Выполняется условие if, т.к. вторая ячейка у нас содержит значение 2, и мы переходим во внутренний цикл, который и будет "просеивать" числа. Рассмотрев код, мы видим, что меняются (помечаются) в ноль все значения массива, кратные двум (4, 6, 8, 10, 12 и так далее). В следующей итерации будет то же самое, но уже с шагом 3, помечаются в ноль значения (6, 9, 12, 15, 18 и так далее).

После окончания работы алгоритма поиска простых чисел, выводим значения элементов массива, не равных нулю на экран. Это и будут найденные простые числа

for(int i = 0; i < size; i++)
	if(array[i] != 0)
		cout << array[i] << endl;

7. При желании, можно как в первой реализации, так и во второй, собрать найденные значения простых чисел в новый массив, который мы создадим динамически. Для этого нужно немного изменить код функции, печатающей результаты работы алгоритма. Вот полученный код

//функция для вывода результатов работы
void printarray(bool myArray[], const int mySize)
{
	int counter = 0;

	//подсчитываем количество найденных простых чисел
	for(int i = 2; i < mySize; i++)
		if(myArray[i] == true)
			counter++;

	//выводим общее количество найденных простых чисел
	cout << endl << "Total: " << counter << endl << endl;

	//динамически создаем массив нужного размера
	int *simple = new int[counter];

	//заполняем созданный массив простыми числами
	for(int i = 2, k = 0; i < mySize; i++)
		if(myArray[i] == true)
			simple[k++] = i;

	//выводим содержимое на экран
	for(int i = 0; i < counter; i++)
		cout << simple[i] << endl;
}

Объявляем счетчик counter, который будет считать количество найденных простых чисел. Затем, зная их количество, мы можем динамически создать массив и наполнить его простыми числами. В конце функции выводим его содержимое на экран, тем самым демонстрируя список найденных величин, присутствующих в интервале от 0 до 1000.

Итак, алгоритм поиска простых чисел мы рассмотрели, в частности для этого было использовано "решето Эратосфена". Все вопросы по алгоритму можно задать на форуме, либо в комментариях.