Пожалуйста помогите улучшить алгоритм задачи “решето Эратосфена” след. способами:
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], кроме самих этих чисел. После такого "просеивания" в множестве М останутся только простые числа.