Помощь - Поиск - Пользователи - Календарь
Полная версия: Решето Эратосфена
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Russia
Здравствуйте!

Пожалуйста помогите улучшить алгоритм задачи “решето Эратосфена” след. способами:

1. Если из множества М удалить все элементы, делящиеся на 2, то нет смысла проверять, делятся ли оставшиеся числа на 4, 6, 8, 10, и т.д.
2. Когда программа проверяет делимость, например, на 50, то она проверяет и числа до 50, что не имеет смысла.

Код программы “решето Эратосфена” представлен ниже:

Код

Program Resheto;
Var
  M : set of byte;
  i, k, N : Integer;
Begin
  Writeln('Введите размер промежутка (до 255) ');
  Readln(N);
  M := [2..N];
  For k := 2 to N div 2 do
    For i := 2 to N do
      If (i mod k=0) and (i<>k)
        Then
          M := M-[i]
  For i := 1 to N do
    If i in M
      Then
        Write(i:3);
  Readln;
End.


Примечание:

Поиск простых чисел с помощью решета Эратосфена в числовом промежутке [1..N].
Простым числом называется число, не имеющее делителей, кроме единицы и самого себя. Подобные задачи могут быть решены методом "решета Эратосфена". Идея метода "решета Эратосфена" заключается в следующем: сформируем множество М, в которое поместим все числа заданного промежутка. Затем последовательно будем удалять из него элементы, кратные 2, 3, 4, и так далее до целой части числа [N/2], кроме самих этих чисел. После такого "просеивания" в множестве М останутся только простые числа.



volvo
Ну, например, так:
Множества, и работа с ними
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.