Алгоритм эратосфена анимация шагов до 50

Скачать:

Вложение	Размер
В презентациях настроена анимация по времени, ускоритьпроцесс можно кликом мышки.	1.1 МБ
В презентациях настроена анимация по времени, ускоритьпроцесс можно кликом мышки.	122.16 КБ

Предварительный просмотр:

Подписи к слайдам:

Предварительный просмотр:

Подписи к слайдам:

Решето Эратосфена Презентация подготовлена учеником 6 А класса МОУ Гимназии №2 г. Железнодорожного Шарагиным Павлом

Решето Эратосфена — это алгоритм нахождения простых чисел до некоторого числа n . Простым называется число, которое можно разделить без остатка только на 1 и на само себя.

Алгоритм нахождения простых чисел Записать в ряд все числа от 2 до n 2 (первое число списка) – простое число. Обозначим его как p . Необходимо вычеркнуть из ряда все числа, делящиеся на р без остатка(2р, 3р, 4р и т.д ) Возьмем следующее незачеркнутое число — 3, и теперь обозначим его как р. Снова вычеркнем числа, делящиеся на р без остатка. Будем повторять этот алгоритм до тех пор, пока р не станет больше, чем n . Все невычеркнутые числа в ряду – Простые.

Разберем алгоритм на примере. Шаг 1й 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 Запишем ряд чисел от 2 до 50 ( n = 50) Первое простое число – 2 (р=2). Вычеркнем из ряда все числа, которые можно разделить на два.

Разберем алгоритм на примере. Шаг 2й 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 Следующее невычеркнутое число – 3 (р=3) – простое. Вычеркнем из ряда все числа, которые можно разделить на три.

Разберем алгоритм на примере. Шаг 3й 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 Следующее невычеркнутое число – 5 (р=5) – простое. Вычеркнем из ряда все числа, которые можно разделить на пять.

Разберем алгоритм на примере. Шаг 4й 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 Продолжим выполнять алгоритм со всеми невычеркнутыми числами, оставшимися в ряду. Все незачеркнутые числа – простые. В нашем случае это 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

—>Просмотров : 5484 | —>Добавил : spring (29.08.2018) (Изменено: 29.08.2018)

Обсуждение вопроса:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Целое число, большее 1, называется простым, если оно не делится нацело ни на какое другое, кроме себя и 1.

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

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа N , который приписывают древнегреческому математику Эратосфену Киренскому. Название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере обработки массива чисел нужные числа (простые) остаются, а ненужные (составные) исключаются.

Сама проблема получения простых чисел занимает ключевое место в математике, на ней основаны некоторые криптографические алгоритмы, например RSA.

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

• Заполнить массив из N элементов целыми числами подряд от 2 до N .
• Присвоить переменной p значение 2 (первого простого числа).
• Удалить из массива числа от p 2 до N с шагом p (это будут числа кратные p : p 2 , p 2 +p , p 2 +2p и т. д.).
• Найти первое неудаленное число в массиве, большее p , и присвоить значению переменной p это число.
• Повторять два предыдущих шага пока это возможно.

Все оставшиеся в массиве числа являются простыми числами от 2 до N

На рисунке проиллюстрирован алгоритм поиска простых чисел. Числа, отмеченные белым, являются удаленными.

Всего ответов: 2