Решето Эратосфена - алгоритм для нахождения все простых чисел до целого числа n
Как работает?
Шаги:
1) Выписать подряд все целые числа от двух до n.
2) Допустим, мы взяли число x, если оно простое, то зачеркиваем все следующие числа до n, делящиеся на x.
3) Находи следующие незачёркнутое число в списке, большее чем x, и присваиваем x это число.
4) Повторять шаги 2 и 3 с новым x, пока это возможно.
5) Незачеркнутые числа — это все простые числа от 2 до n.
Допустим, мы хотим найти все простые числа до 50, тогда выполним следующее:
1) Выписываем подряд все целые числа от двух до 30.
2) Допустим, мы взяли число 2, если оно простое, то зачеркиваем все следующие числа до 30, делящиеся на 2.
3) Находи следующие незачёркнутое число в списке, большее чем 2, и всместо двух берем это число.
4) Повторяем шаги 2 и 3 с новым числом, пока это возможно (вместо двух брать любое другое число).
5) Незачеркнутые числа — это все простые числа от 2 до 30