Задача: Вывести на экран все простые трехзначные числа.
Как говорит нам наука “математика” – простое число, это такое число которое делится только на единицу и на само себя.
Примером такого числа могут служить числа: 1, 3, 5, 7, 11, 13, 17 и т.д.
Универсального алгоритма, который позволял бы без ряда проверок (попыток деления) проверить является ил число простым – нет.
В самом простом в реализации случае проверка сводится к тому, чтобы проверить делится ли число N хотя бы на одно число из промежутка [2,N). Если делится - значит число не простое.
Существует ряд алгоритмов оптимизирующих такую проверку. Подробно о них можно почитать в Википедии - Тест простоты
В данной конкретной задачи нет какой-либо необходимости оптимизации, так-как диапазон ограничен трехзначными числами.
План решения:
1. В цикле от 999 до 101 делаем следующее
1.1. Считаем, что число простое
1.2. В цикле от N-1 до 2 проверяем остаток от деления числа. Если остаток равен нулю - считаем что число не простое и выходим из цикла.
1.3. Если число простое, то выводим его на экран
Реализация на Turbo Pascal 7:
program treh_znachnie_prostie;
var n,i:integer;
prostoe:boolean;
begin
n:=999;
while n>100 do
begin
prostoe:=true;
i:=n-1;
while (i>1) and (prostoe = true) do
if n mod i = 0 then
prostoe:=false
else
i:=i-1;
if prostoe=true then
write(n:5);
n:=n-1;
end;
readln;
end.
Блок-схема:
Блок-схема вывода всех простых трехзначных чисел
Блоксхема создана с помощью редактора http://www.gliffy.com
Метки: алгоритм