Напишите функцию eratosthenes(N), воспроизводящую данный алгоритм

@Pavlin234 · Регистрация: 12.03.2017

Студворк — интернет-сервис помощи студентам

В 235 году до н.э. греческий ученый Эратосфен изобрел следующий способ нахождения простых чисел на промежутке от 1 до заданного N:

1. Выписать все целые числа 2,...,N.

2. Зачеркнуть все числа, кратные i = 2 - первому простому числу.

3. Найти первое незачёркнутое число в списке, большее чем i, и присвоить значению переменной i это число.

4. Повторять шаги 2 и 3, пока это возможно.

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

Напишите функцию eratosthenes(N), воспроизводящую данный алгоритм. Ваша функция должна через пробел печатать числа в том порядке, в котором их вычеркивает из списка оригинальный алгоритм. Например, если N = 10, то числа будут вычеркиваться в таком порядке: 4 6 8 10 9.
Пример
Ввод
15
Вывод
4 6 8 10 12 14 9 15

@regio1961 · 12.12.2017, 21:14

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import math
 
def Eratosthenes( N ):
    A = [ n for n in range( 2, N + 1 )]
    sqrt_N = math.sqrt( N )
    i = 2
    while ( i <= sqrt_N ):
        for a in A[ i - 2 : N - 1 : ]:
            if ( a != 0 ) and ( a % i == 0 ) and ( a != i ):
                print( a, end = " " )
                A[ A.index( a ) ] = 0
        i += 1
    print( "\n" )
 
N = 15
Eratosthenes( N )

@Shamil1 · 13.12.2017, 23:46

regio1961,
Это не то. В алгоритме Эратосфена деление не используется.

@Shamil1 · 14.12.2017, 09:07

Python
1
2
3
4
5
6
7
8
9
10
11
def Eratosthenes( n ):
    a = [ n for n in range(n + 1)]
    a[0] = 0; a[1] = 0;
    for i in range(2, len(a)):
        if a[i] > 0:
            for j in range(i * i, n + 1, i):
                if a[j] > 0:
                    print(a[j], end=" ")
                    a[j] = 0
    print()
    return [x for x in a if x > 0]

@regio1961 · 14.12.2017, 14:00

Сообщение от Shamil1

В алгоритме Эратосфена деление не используется.

Неужели?

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

Где здесь сказано, что деление не используется?

@Shamil1 · 14.12.2017, 14:09

Сообщение от regio1961

Где здесь сказано, что деление не используется?

А зачем об этом говорить? Тот, кто читает алгоритм, и так видит, что в нём используется, а что нет. А писать длинный список того, что не используется, нет смысла (всё равно он будет неполным... даже если начать с котиков).

@regio1961 · 14.12.2017, 14:18

Сообщение от Shamil1

А зачем об этом говорить?

А зачем говорить то, чего нет? В алгоритме отсеиваются кратные числа, как это делать -- вопрос реализации, никто не запрещает делать это целочисленным делением. Разумеется, можно, при желании, избавиться от деления и еще провести множество оптимизаций, даже котиков использовать.

@Shamil1 · 14.12.2017, 15:45

Сообщение от regio1961

В алгоритме отсеиваются кратные числа, как это делать -- вопрос реализации, никто не запрещает делать это целочисленным делением

Нет. Суть алгоритма в том, как это делается. В данном алгоритме это делается зачёркиванием чисел, кратных простым.

@regio1961 · 14.12.2017, 15:55

Сообщение от Shamil1

Нет. Суть алгоритма в том, как это делается. В данном алгоритме это делается зачёркиванием чисел, кратных простым.

Суть алгоритма -- в его цели, цель: найти простые числа на заданном отрезке, "зачеркивание" -- средство, а не цель. Решение о том зачеркнуть (удалить, изъять, выколоть его стилом, как делали во времена Эратосфена... ) число или нет на основе чего принимается? Котики подсказывают?

@Shamil1 · 14.12.2017, 16:01

Сообщение от regio1961

Суть алгоритма -- в его цели

То есть, Вы утверждаете, каким бы способом я не искал нод, это будет алгоритм Евклида?

Сообщение от regio1961

Решение о том зачеркнуть (удалить, изъять, выколоть его стилом, как делали во времена Эратосфена... ) число или нет на основе чего принимается?

"3. Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …)."

@regio1961 · 14.12.2017, 16:07

Сообщение от Shamil1

То есть, Вы утверждаете, каким бы способом я не искал нод, это будет алгоритм Евклида?

Нет, я утверждаю, что каким бы способом ни искать НОД, это будет алгоритм нахождения наибольшего общего делителя, ибо такова его цель. В частности, можно применить и алгоритм Евклида. Дальнейшую дискуссию считаю излишней.

@Shamil1 · 14.12.2017, 16:22

Сообщение от regio1961

Нет

Почему же Вы утверждаете, что предложенный Вами алгоритм составления списка простых чисел является алгоритмом "Решето Эратосфена"?

з.ы. На всякий случай:
Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата.

@vakkrehevn · 17.01.2021, 13:04

а что ты делаешь в 8 строке в скобках[]

Новые блоги и статьи Все статьи Все блоги /
BOINC: 22 года — и всё ещё работает Programma_Boinc 12.03.2026 BOINC: 22 года — и всё ещё работает Дэвид Андерсон написал ретроспективу. Кратко: в 2001 году он ушёл из United Devices, где был CTO, и за несколько месяцев написал ядро BOINC — клиент, сервер,. . .	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

@Pavlin234 10 / 59 / 21 Регистрация: 12.03.2017 Сообщений: 514

	Напишите функцию eratosthenes(N), воспроизводящую данный алгоритм 12.12.2017, 16:00. Показов 6974. Ответов 12 Метки нет (Все метки) В 235 году до н.э. греческий ученый Эратосфен изобрел следующий способ нахождения простых чисел на промежутке от 1 до заданного N: 1. Выписать все целые числа 2,...,N. 2. Зачеркнуть все числа, кратные i = 2 - первому простому числу. 3. Найти первое незачёркнутое число в списке, большее чем i, и присвоить значению переменной i это число. 4. Повторять шаги 2 и 3, пока это возможно. После завершения алгоритма незачеркнутыми останутся все простые числа, меньшие либо равные N. Напишите функцию eratosthenes(N), воспроизводящую данный алгоритм. Ваша функция должна через пробел печатать числа в том порядке, в котором их вычеркивает из списка оригинальный алгоритм. Например, если N = 10, то числа будут вычеркиваться в таком порядке: 4 6 8 10 9. Пример Ввод 15 Вывод 4 6 8 10 12 14 9 15 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	13.12.2017, 23:46
	regio1961, Это не то. В алгоритме Эратосфена деление не используется. 0

@vakkrehevn 0 / 0 / 0 Регистрация: 17.01.2021 Сообщений: 24
	17.01.2021, 13:04
	а что ты делаешь в 8 строке в скобках[] 0