DRAKON.SU
https://forum.drakon.su/

Решето Эратосфена
https://forum.drakon.su/viewtopic.php?f=228&t=6702
Страница 1 из 1

Автор:  Дмитрий Бардынин [ Вторник, 22 Октябрь, 2019 13:34 ]
Заголовок сообщения:  Решето Эратосфена

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n.

Изображение

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

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

Используя переменную i вместо p, за основу возьмем усовершенствованный алгоритм, когда на шаге № 3 числа можно зачеркивать начиная сразу с квадрата числа i, потому что все составные числа меньше него уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда квадрат i станет больше, чем n
Вложение:
Решето.JPG
Решето.JPG [ 108.66 КБ | Просмотров: 3441 ]

В редакторе DrakonBar используем генератор "Processing.org"
Вложение:
Решето2.JPG
Решето2.JPG [ 77.23 КБ | Просмотров: 3441 ]

Код:
 
// Generator adopted by Bardynin Dmitry, Astrakhan-Sochi, 2019, ver.0.11
 

// Resheto AEratosfena
void setup(  ) {
    int n = 100000000;
    //Sozdaem massiv n-jacheek
    boolean[] a = new boolean[n+1];
    int i = 2;
    while (true) {
        a[i] = true;
        i = i + 1;
        if (i<=n) {
        } else {
            break;
        }
    }
    i = 2;
    while (true) {
        if (a[i] == true) {
            int j = i*i;
            while (true) {
                a[j] = false;
                j = j + i;
                if (j <= n) {
                } else {
                    break;
                }
            }
        } else {
        }
        i = i + 1;
        if (i*i <= n) {
        } else {
            break;
        }
    }
    i = 2;
    while (true) {
        if (a[i] == true) {
            print('\t'); // output_simple
            print(i); // output_simple
        } else {
        }
        i = i + 1;
        if (i<=n) {
        } else {
            break;
        }
    }
}

void draw () {}

Автор:  Владимир Паронджанов [ Вторник, 22 Октябрь, 2019 13:51 ]
Заголовок сообщения:  Re: Решето Эратосфена

Последняя ветка не нужна

Автор:  Дмитрий Бардынин [ Вторник, 22 Октябрь, 2019 13:56 ]
Заголовок сообщения:  Re: Решето Эратосфена

Да, пожалуй :)

Вложения:
Решето3.JPG
Решето3.JPG [ 156.52 КБ | Просмотров: 3428 ]

Автор:  LKom [ Вторник, 22 Октябрь, 2019 14:10 ]
Заголовок сообщения:  Re: Решето Эратосфена

Полагаю, для Решето.JPG алгоритм неправильный.

j=i*i
для a[j] индекс обязательно выйдет за пределы массива.

Для Решето3.JPG алгоритм неправильный.
Для i=29 не будет простым числом.
---
Дракон обеспечивает некоторую наглядность, но не спасает от ошибок в алгоритме.

Дмитрий Бардынин писал(а):
Да, пожалуй :)
Больше надо думать.

Что за хвост в Дракон схеме в последней ветке правее "Нет"?

Автор:  Дмитрий Бардынин [ Вторник, 22 Октябрь, 2019 14:34 ]
Заголовок сообщения:  Re: Решето Эратосфена

LKom писал(а):
Полагаю, для Решето.JPG алгоритм неправильный.

j=i*i
для a[j] индекс обязательно выйдет за пределы массива.

Для Решето3.JPG алгоритм неправильный.
Для i=29 не будет простым числом.
---
Дракон обеспечивает некоторую наглядность, но не спасает от ошибок в алгоритме.

Дмитрий Бардынин писал(а):
Да, пожалуй :)
Больше надо думать.

Что за хвост в Дракон схеме в последней ветке правее "Нет"?

Хвост вылез при вырезании лишней ветки, форматирование сдвинулось. Бывает. Поправил.

А вот про думать - это скорее к Вам. Переменная j первоначально не превысит 4, затем она увеличивается на i, а потом Вопрос отсечет все лишнее.
Конечно, можно поставить "защиту от дурака" на случай n<4, но в базовый алгоритм Эратосфена эта проверка не входит.

И что не так с числом 29? У меня все правильно считается. И при N=30, и при N=29
Вложение:
Решето4.JPG
Решето4.JPG [ 60.71 КБ | Просмотров: 3426 ]


Собственно, у меня указана диаграмма для улучшенного алгоритма. Выглядит так:
Код:
Вход: натуральное число 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.

Автор:  Дмитрий Бардынин [ Вторник, 22 Октябрь, 2019 14:57 ]
Заголовок сообщения:  Re: Решето Эратосфена

По правильности работы алгоритма могу сообщить: я на его основе сразу генерирую программу, и сразу запускаю. С хвостиком так не сделал, виноват, вот и осталась помарка. В целом: выход корректный. Дам заготовку детишкам на клубе, пусть диаграмму построят.

Автор:  LKom [ Вторник, 22 Октябрь, 2019 15:12 ]
Заголовок сообщения:  Re: Решето Эратосфена

Думать надо.

Смотришь на схему и невозможно думать!
Упоминаются переменные: n, i, j. Смысл и назначение переменных не раскрыто.
Т.е. нет алгоритма в терминах прикладной области.

Автор:  Дмитрий Бардынин [ Вторник, 22 Октябрь, 2019 16:03 ]
Заголовок сообщения:  Re: Решето Эратосфена

Переменные я использовал строго по примеру из Вики. Иначе мне пришлось бы переписывать тот пример, а это, к.м.к., в моем случае не основная задача.

Предлагаете совсем не использовать переменные? Или заменить их на говорящие имена? У программистов имена переменных n, i, j - довольно популярны, и обычно означают: размер/число, счетчик цикла, счетчик вложенного цикла.

Автор:  Владимир Паронджанов [ Пятница, 01 Ноябрь, 2019 20:16 ]
Заголовок сообщения:  Re: Решето Эратосфена

Замечание по названию

Решето Эратосфена — это специальный математический термин, известный в узком кругу математиков. Это своего рода ребус.
Данный термин не удовлетворяет критерию "доступность для народа".

В иконе Заголовок не следует писать специальные термины, понятные только для специалистов и непонятные для всех остальных.

А что надо написать?

Вот что:
Цитата:
Нахождение всех простых чисел до числа n

В первой ветке добавить икону Комментарий, а в ней можно написать пояснение
Цитата:
Алгоритм нахождения всех простых чисел до некоторого целого числа n называется "Решето Эратосфена".

Автор:  Дмитрий Бардынин [ Четверг, 07 Ноябрь, 2019 13:28 ]
Заголовок сообщения:  Re: Решето Эратосфена

Вложение:
решето.PNG
решето.PNG [ 42.75 КБ | Просмотров: 3385 ]

Автор:  Владимир Паронджанов [ Четверг, 07 Ноябрь, 2019 13:41 ]
Заголовок сообщения:  Re: Решето Эратосфена

В первой ветке шампур жирный, в остальных шампур бледный (нежирный).

Я понял, что вы жирность шампура устанавливаете вручную.

Желательно в редакторе DrakonBar предусмотреть безусловную АВТОМАТИЧЕСКУЮ установку жирности шампура.

Автор:  Дмитрий Бардынин [ Четверг, 07 Ноябрь, 2019 15:25 ]
Заголовок сообщения:  Re: Решето Эратосфена

Автоматически, но иногда при быстром перемещении блоков не срабатывает обновление диаграммы. Исправлю в новых версиях.

Вложение:
решето.PNG
решето.PNG [ 44.43 КБ | Просмотров: 3378 ]

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/