Проверка на простоту

Поиск простых чисел методом перебора делителей.

Простое число — это число, которое делится только на 1 и на само себя. Например: 2, 3, 5, 7, 11, 13...

Разбор

Главная программа

Перебираем все числа от 2 до 100 и выводим только простые:

алг
нач
    цел i
    вывод "Простые числа до 100:", нс
    нц для i от 2 до 100
        если простое(i)
        то
            вывод i, " "
        все
    кц
    вывод нс
кон

Для каждого числа i вызываем функцию простое, которая возвращает истина или ложь
Если число простое — выводим его

Функция простое

алг лог простое(цел n)
нач
    если n < 2
    то
        знач := ложь
    иначе
        цел i
        знач := истина
        нц для i от 2 до int(sqrt(n))
            если mod(n, i) = 0
            то
                знач := ложь
            все
        кц
    все
кон

алг лог — функция возвращает логическое значение (истина / ложь)
Числа меньше 2 не являются простыми
sqrt(n) — квадратный корень из $n$, int(...) — округление вниз до целого
mod(n, i) = 0 — проверяем, делится ли $n$ на $i$ без остатка. Если да — число не простое

Почему проверяем делители только до $\sqrt{n}$? Если $n$ делится на какое-то число $d$, то $n = d \times k$. Одно из чисел $d$ или $k$ обязательно не больше $\sqrt{n}$. Поэтому если до $\sqrt{n}$ делителей не нашлось — их нет вообще.

Например, для $n = 36$: $\sqrt{36} = 6$. Пары делителей: $2 \times 18$, $3 \times 12$, $4 \times 9$, $6 \times 6$ — в каждой паре хотя бы одно число $\le 6$.

Полная программа

алг
нач
    цел i
    вывод "Простые числа до 100:", нс
    нц для i от 2 до 100
        если простое(i)
        то
            вывод i, " "
        все
    кц
    вывод нс
кон

алг лог простое(цел n)
нач
    если n < 2
    то
        знач := ложь
    иначе
        цел i
        знач := истина
        нц для i от 2 до int(sqrt(n))
            если mod(n, i) = 0
            то
                знач := ложь
            все
        кц
    все
кон