Что такое решето Эратосфена? (обьясните и помогите понять как решается?)

Question

Что такое решето Эратосфена? (обьясните и помогите понять как решается?)

Answer 1

Решето Эратосфена - алгоритм для нахождения все простых чисел до целого числа 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

Comments

Что значит n ?

---

n - число, до которого надо найти все простые числа

---

Можешь привести пример решения?

---

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

---

до 30

Answer 2

Решето Эратосфена - алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому. Оно подразумевает фильрацию всех чисел за исключением простых.

---

Comments

Можешь привести пример?

---

По мере прохождения списка нужные числа остаются, а ненужные (они называются составными) исключаются.

---

Я имею в веду решить,что то?

---

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

Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
Пусть переменная p изначально равна двум — первому простому числу.
Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).
Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
Повторять шаги 3 и 4, пока возможно.