понедельник, 3 июня 2013 г.

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

Данный код выводит все простые числа в интервале от 2 ... number.


#include <iostream>
using namespace std;

void sieveOfEratosthenes(int arr[], int size);
void print(int arr[], int size);
int main()
{
cout << "Enter a number: ";
int number = 0;
cin >> number;
int *arr = new int[number];

sieveOfEratosthenes(arr, number);
print(arr, number);

return 0;
}

void sieveOfEratosthenes(int arr[], int size)
{
for (int i = 2; i < size; ++i)
{
arr[i] = 1;
}

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

void print(int arr[], int size)
{
for (int i = 2; i < size; ++i)
{
if (1 == arr[i])
{
cout << i << ' ';
}
}
cout << endl;
}

Сначала массив инициализируется единицами (признак, что число простое). Далее по ходу итераций, значение в ячейке массива меняется на нуль, т.е. число не является простым.