DRAKON.SU

Текущее время: Четверг, 28 Март, 2024 20:58

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 12 ] 
Автор Сообщение
 Заголовок сообщения: Решето Эратосфена
СообщениеДобавлено: Вторник, 22 Октябрь, 2019 13:34 

Зарегистрирован: Пятница, 08 Декабрь, 2017 18:24
Сообщения: 439
Откуда: Астрахань-Сочи
Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа 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 КБ | Просмотров: 7745 ]

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

Код:
 
// 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 () {}


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена
СообщениеДобавлено: Вторник, 22 Октябрь, 2019 13:51 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
Последняя ветка не нужна


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена
СообщениеДобавлено: Вторник, 22 Октябрь, 2019 13:56 

Зарегистрирован: Пятница, 08 Декабрь, 2017 18:24
Сообщения: 439
Откуда: Астрахань-Сочи
Да, пожалуй :)


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


Последний раз редактировалось Дмитрий Бардынин Вторник, 22 Октябрь, 2019 14:28, всего редактировалось 1 раз.
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена
СообщениеДобавлено: Вторник, 22 Октябрь, 2019 14:10 

Зарегистрирован: Среда, 07 Январь, 2015 14:53
Сообщения: 1356
Полагаю, для Решето.JPG алгоритм неправильный.

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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена
СообщениеДобавлено: Вторник, 22 Октябрь, 2019 14:34 

Зарегистрирован: Пятница, 08 Декабрь, 2017 18:24
Сообщения: 439
Откуда: Астрахань-Сочи
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 КБ | Просмотров: 7730 ]


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена
СообщениеДобавлено: Вторник, 22 Октябрь, 2019 14:57 

Зарегистрирован: Пятница, 08 Декабрь, 2017 18:24
Сообщения: 439
Откуда: Астрахань-Сочи
По правильности работы алгоритма могу сообщить: я на его основе сразу генерирую программу, и сразу запускаю. С хвостиком так не сделал, виноват, вот и осталась помарка. В целом: выход корректный. Дам заготовку детишкам на клубе, пусть диаграмму построят.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена
СообщениеДобавлено: Вторник, 22 Октябрь, 2019 15:12 

Зарегистрирован: Среда, 07 Январь, 2015 14:53
Сообщения: 1356
Думать надо.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена
СообщениеДобавлено: Вторник, 22 Октябрь, 2019 16:03 

Зарегистрирован: Пятница, 08 Декабрь, 2017 18:24
Сообщения: 439
Откуда: Астрахань-Сочи
Переменные я использовал строго по примеру из Вики. Иначе мне пришлось бы переписывать тот пример, а это, к.м.к., в моем случае не основная задача.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена
СообщениеДобавлено: Пятница, 01 Ноябрь, 2019 20:16 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
Замечание по названию

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

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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена
СообщениеДобавлено: Четверг, 07 Ноябрь, 2019 13:28 

Зарегистрирован: Пятница, 08 Декабрь, 2017 18:24
Сообщения: 439
Откуда: Астрахань-Сочи
Вложение:
решето.PNG
решето.PNG [ 42.75 КБ | Просмотров: 7689 ]


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена
СообщениеДобавлено: Четверг, 07 Ноябрь, 2019 13:41 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
В первой ветке шампур жирный, в остальных шампур бледный (нежирный).

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена
СообщениеДобавлено: Четверг, 07 Ноябрь, 2019 15:25 

Зарегистрирован: Пятница, 08 Декабрь, 2017 18:24
Сообщения: 439
Откуда: Астрахань-Сочи
Автоматически, но иногда при быстром перемещении блоков не срабатывает обновление диаграммы. Исправлю в новых версиях.

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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2008-2024, участники конференции «DRAKON.SU», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB