Task 33. Вывести все простые числа до N

Задача: Вывести все простые числа до N, N - натуральное число.

Идея: Простое число - натуральное число (больше 1), называется простым, если оно ни на что не делится, кроме себя и 1.

Самое простое решение это перебор.

Для очень больших чисел – существуют более эффективные алгоритмы проверки простоты числа, например, решето Эратосфена :

1. Для всех чисел от 2 до N.
2. Пусть p = 2, первое простое число
3. Зачеркнуть все последующие числа в списке с разницей в p, т.е. 2*p, 3*p, 4*p и т.д.
4. Поменять значение p на первое не зачеркнутое значение число после p.
5. Повторить шаги 3-4. Оставшиеся не зачеркнутые числа будут простыми.

Смотри схематический рисунок алгоритма:

Реализация:

1. Простой перебор

https://gist.github.com/unilecs/9a0ffc6cdf119661cd4e804c8719453f

Тест:

https://dotnetfiddle.net/0QdVqU

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

https://gist.github.com/unilecs/8038467ea894e5ed50c7dd691493a420

Тест:

https://dotnetfiddle.net/zNOsUW