LKom писал(а):
Полагаю, для Решето.JPG алгоритм неправильный.
j=i*i
для a[j] индекс обязательно выйдет за пределы массива.
Для Решето3.JPG алгоритм неправильный.
Для i=29 не будет простым числом.
---
Дракон обеспечивает некоторую наглядность, но не спасает от ошибок в алгоритме.
Дмитрий Бардынин писал(а):
Да, пожалуй
Больше надо думать.
Что за хвост в Дракон схеме в последней ветке правее "Нет"?
Хвост вылез при вырезании лишней ветки, форматирование сдвинулось. Бывает. Поправил.
А вот про думать - это скорее к Вам. Переменная j первоначально не превысит 4, затем она увеличивается на i, а потом Вопрос отсечет все лишнее.
Конечно, можно поставить "защиту от дурака" на случай n<4, но в базовый алгоритм Эратосфена эта проверка не входит.
И что не так с числом 29? У меня все правильно считается. И при N=30, и при N=29
Вложение:
Решето4.JPG [ 60.71 КБ | Просмотров: 7825 ]
Собственно, у меня указана диаграмма для улучшенного алгоритма. Выглядит так:
Код:
Вход: натуральное число n
Пусть A — булевый массив, индексируемый числами от 2 до n,
изначально заполненный значениями true.
для i := 2, 3, 4, ..., пока i^2 ≤ n:
если A[i] = true:
для j := i^2, i^2 + i, i^2 + 2*i, ..., пока j ≤ n:
A[j] := false
Выход: числа i, для которых A[i] = true.