Задача вполне тривиальная, потому приведу здесь исходный код и немного описания только с целью, чтобы: кто не знал — тот освоил, кто забыл — тот вспомнил, а кто знает и не забыл — тот закрыл и не читал
Немного о сути метода:
Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому.
Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:
- Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
- Пусть переменная p изначально равна двум — первому простому числу.
- Вычеркнуть из списка все числа от 2p до n, делящиеся на p (то есть, числа 2p, 3p, 4p, …)
- Найти первое не вычеркнутое число, большее чем p, и присвоить значению переменной p это число.
- Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n
- Все не вычеркнутые числа в списке — простые числа.
- Ну, и, пожалуй, достаточно. Суть, я думаю, ясна.
Исходный код:
class Eratosfen
{
List<int> simple;
public Eratosfen(int MaxNumber)
{
simple = new List<int>();
for (int i = 1; i < MaxNumber; i++)
simple.Add(i);
DoEratosfen();
}
int Step(int Prime, int startFrom)
{
int i = startFrom+1;
int Removed = 0;
while (i < simple.Count)
if (simple[i] % Prime == 0)
{
simple.RemoveAt(i);
Removed++;
}
else
i++;
return Removed;
}
void DoEratosfen()
{
int i=1;
while (i < simple.Count)
{
Step(simple[i], i);
i++;
}
}
public int[] Simple
{
get
{
return simple.ToArray();
}
}
}
</int></int>
Как видно из исходного кода, выше приведён класс Eratosfen. Использовать данный класс нужно так:
Создать экземпляр класса Eratosfen (в качестве параметра в конструктор передаётся значение числа, до которого будет вестись поиск простых чисел)
Используя свойство Simple, получаем доступ к массиву простых чисел.
Всё просто!
Вот как это может выглядить «вживую»:
(new Eratosfen(999)).Simple
О преимуществах и недостатках «решета Эратосфена» спорить не будем, потому что:
- Глупо;
- Нету смысла;
- Каждый сам выбирает.