Простые числа. Решето Эратосфена

Вернемся к простым числам. Есть алгоритм, по которому легко вычислить все простые числа до какого-то заданного числа N - это решето Эрастофена. Суть его в следующем: запишем все числа от 1 до N в ряд. Так как число 1 не простое, то его не рассматриваем, т.е. вычеркиваем (число, которое вычеркиваем - подчеркнуто, а простое - выделено полужирным).

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...,N

1. Берем следующее невычеркнутое число 2.

2. Проверяем все числа от 3 до N на делимость на 2. Если число делится на 2 без остатка, то вычеркиваем его.

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...,N

4. Переходим к следующему невычеркнутому числу - это 3, и повторяем п.2, но уже числа проверяем с 4 до N и проверяем делимость на 3.

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...,N

5. Переходим к следующему невычеркнутому числу - это 5, и повторяем п.2, но уже числа проверяем с 6 до N и проверяем делимость на 5.

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...,N

и т.д.

Видно, что алгоритм можно оформить в виде циклов. Для проверки делимости можно использовать операцию mod - взятие остатка.

Вопрос: как оформить процесс вычеркивания в Паскале?

Есть несколько способов: с помощью структурированных типов множество, массив или строки.

C помощью множества

Множество целых чисел не превышает значения 255. Если число не простое - исключаем его из множества. Перед работой присваиваем множеству диапазон чисел от 2 до N. :

Var M:set of byte;

    i,k,N:byte;

begin

{ввод и инициализация}

    readln(N);

    M:=[2..N];

    k:=2;

{алгоритм решето Эратосфена}

    repeat

    for i:=k+1 to N do

       if (i in M) and(i mod k=0) then M:=M-[i];

    inc(k);

    while (k<=N) and not (k in M) do inc(k);

    until k>N;

{вывод ряда простых чисел}

    for i:=2 to N do if i in M then write(' ',i);

end.

C помощью массива

Лучше использовать массив с элементами логического типа. Будем считать, что на i-ом месте массива P стоит true (или 1) если число простое, иначе false (или 0). Перед работой массив нужно  "проинициализировать" значениями true (или 1), т.е. считаем, что все числа простые (как при доказательстве от противного):

Var P:array [2..65535] of boolean;

    i,k,N:word;

begin

{ввод и инициализация}

    readln(N);

    fillchar(P,N,1);

    k:=2;

{алгоритм решето Эратосфена}

    repeat

    for i:=k+1 to N do

       if P[i] and(i mod k=0) then P[i]:=false;

    inc(k);

    while (k<=N) and (not P[k]) do inc(k);

    until k>N;

{вывод ряда простых чисел}

    for i:=2 to N do if P[i] then write(' ',i);

end.

C помощью строк

Будем считать, что на i-ом месте строки S стоит '*' если число простое, иначе ' ' (пробел). Перед работой со строкой нужно ее "инициализировать" символами '*', т.е. считаем, что все числа простые (как при доказательстве от противного). Кроме этого нужно знать, что строка содержит не более 255 символов (как сделать еще больше? Создать массив символов - это другой способ):

Var S:string[255];

    i,k,N:byte;

begin

{ввод и инициализация}

    readln(N);

    fillchar(S,N,'*');

    S[1]:=' ';k:=2;

{алгоритм решето Эратосфена}

    repeat

    for i:=k+1 to N do

       if (S[i]='*')and(i mod k=0) then S[i]:=' ';

    inc(k);

    while (k<=N) and(S[k]=' ') do inc(k);

    until k>N;

{вывод ряда простых чисел}

    for i:=2 to N do if S[i]='*' then write(' ',i);

end.

Я специально привела три способа, чтобы показать какие есть возможности у Паскаля для реализации этого алгоритма. каждый алгоритм имеет свои ограничения на конечное число: 255 и 65535. Можно попробовать написать программу с использованием указателей на ячейку памяти. Тогда ограничение для чисел здесь увеличивается до типа longint или comp, а если написать операцию проверки делимости для вещественных чисел, то и для extended (самого большого числа). Но для вещественных чисел нужно менять цикл for на While, что может привести к увеличению времени работы алгоритма.

Пробуйте.

PS: Кроме этого разбора я показала один из приемов в обучении: чтобы запомнить алгоритм - нужно его попробовать написать другим способом и если через некоторое время переменные, операторы, типы будут схожи, то вы выработали свой стиль программирования и запомнили алгоритм. Удачи.