Задача: Вывести на экран все простые трехзначные числа.
Как говорит нам наука «математика» – простое число, это такое число которое делится только на единицу и на само себя.
Примером такого числа могут служить числа: 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
Метки: алгоритм