Все числа указанного интервала можно рассматривать как множество и в дальнейшем из этого множества будем исключать (отсеивать) все составные числа. Простые числа выводятся по 10 в строке, как только значение счетчика становится кратным 10, курсор переводится на новую строку. Рекурсия это такой способ организации обработки данных, при котором программа вызывает сама себя непосредственно, либо с помощью других программ.

Алгоритмы нахождения простых чисел

Простые числа – это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число.

Существует множество задач, связанных с простыми числами, и хотя формулируются они достаточно просто, решить их бывает очень трудно. Некоторые свойства простых чисел еще не открыты. Это побудило немецкого математика Германа Вейля (Wayl, 1885-1955) так охарактеризовать простые числа: «Простые числа – это такие существа, которые всегда склонны прятаться от исследователя».

Во все времена люди хотели найти как можно большее простое число. Пока люди считали только при помощи карандаша и бумаги, им нечасто удавалось обнаружить новые простые числа. До 1952 г. самое большое известное простое число состояло из 39 цифр. Теперь поиском все больших простых чисел занимаются компьютеры. Это может представлять интерес для любителей рекордов.

Не будем гнаться за рекордами, а рассмотрим несколько алгоритмов нахождения простых чисел.

Мнение эксперта

Черноволов Василий Петрович, эксперт по вопросам мобильной связи и интернета

Все сложные вопросы мы с вами решим вместе.

Задать вопрос эксперту

Составить программу поиска четырехзначных чисел, которые при делении на 133 дают в остатке 125, а при делении на 134 дают в остатке 111. Если вам нужна бесплатная консультация, пишите мне!

Алгоритмы нахождения простых чисел

1. Вводим правую границу диапазона – m;
2. Записываем двойку и тройку в файл;
3. Пока очередное нечетное число i
4. проверять очередное нечетное число на наличие делителей из данного файла;
5. если есть делители, рассматривать очередное нечетное число, если нет — производить дозапись в “хвост” файла.

Задача 1. Определение простого числа.

Составить программу, которая будет проверять, является ли введенное число простым.

Составить программу, которая напечатает все простые числа в заданном интервале [2, m], для m>3 и подсчитает их количество.

Для реализации данного алгоритма необходимо проверить каждое число, находящееся в данном интервале, — простое оно или нет. Однако для этого машине пришлось бы потратить много времени. Поэтому подумаем, каким образом можно оптимизировать алгоритм, описанный в задаче 1, применительно к задаче 2?

Будем использовать следующие приемы оптимизации алгоритма:

1. рассматривать только нечетные числа;
2. использовать свойство: наименьшее число, на которое делится натуральное число n, не превышает целой части квадратного корня из числа n;
3. прерывать работу цикла, реализующего поиск делителей числа, при нахождении первого же делителя с помощью процедуры Break, которая реализует немедленный выход из цикла и передает управление оператору, стоящему сразу за оператором цикла.

Как правило, учащиеся сами догадываются о приемах №1 и №3, но не всегда знают, как реализовать в программе досрочное завершение цикла, прием же №2 для них не очевиден, поэтому, возможно, учителю следует остановиться на нем более подробно или же привести полное доказательство этого утверждения.

Счетчик чисел будет находиться в переменной k. Когда очередное простое число найдено, он увеличивается на 1. Простые числа выводятся по 10 в строке, как только значение счетчика становится кратным 10, курсор переводится на новую строку.

15. Поле шахматной доски определяется парой натуральных чисел, каждое из которых не превосходит 8. Напишите программу, которая по введённым координатам двух полей (k, l) и (m, n) определяет, имеют ли эти поля один цвет. Все ранее рассматриваемые программы имели линейную структуру все инструкции выполнялись последовательно одна за одной, каждая записанная инструкция обязательно выполнялась. Мы же помимо чисел используем кучу разных типов данных числа, строки, списки, словари, кортежи последние 3 будут обсуждаться дальше в курсе.

Тип заданий 20.2 — Программирование — практика

Задача 20.2_2

Задача 20.2_3

Задача 20.2_4

Задача 20.2_5

Задача 20.2_6

Задача 20.2_7

Задача 20.2_8

Мнение эксперта

Черноволов Василий Петрович, эксперт по вопросам мобильной связи и интернета

Все сложные вопросы мы с вами решим вместе.

Задать вопрос эксперту

Все инструкции, которые относятся к одному блоку, должны иметь равную величину отступа, то есть одинаковое число пробелов в начале строки. Если вам нужна бесплатная консультация, пишите мне!

3.4. Программирование разветвляющихся алгоритмов | Условный и составной операторы

Операторы сравнения возвращают значения специального логического типа bool. Значения логического типа могут принимать одно из двух значений: True (истина) или False (ложь) . Существует множество задач, связанных с простыми числами, и хотя формулируются они достаточно просто, решить их бывает очень трудно. Оптимизировать алгоритм задачи 4 следующим образом найденные простые числа записывать в файл, делимость очередного кандидата проверять только на числа из этого файла.

Вопросы и задания

1. Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Используйте эти материалы при подготовке ответов на вопросы и выполнении заданий.

2. Как на языке Паскаль записывается полное и неполное ветвление?

3. Является ли условным оператором следующая последовательность символов?

а) if хthen х:=0 else read (у)
б) if х>=у then х:=0; у:=0 else write (z)
в) if xthen a:=a+l

4. Что такое составной оператор? Для чего он используется в условном операторе?

5. Используя составной оператор, упростите следующий фрагмент программы:

if a>b then с:=1;
if a>b then d:=2;
if athen c:=3;
if athen d:=4

6. Дано трёхзначное число. Напишите программу, которая определяет:

а) есть ли среди цифр заданного целого трёхзначного числа одинаковые;

б) является ли число «перевёртышем», т. е. числом, десятичная запись которого читается одинаково слева направо и справа налево.

7. Даны две точки в плоской прямоугольной системе координат. Напишите программу, определяющую, которая из точек находится ближе к началу координат.

8. Даны три натуральных числа. Напишите программу, определяющую, существует ли треугольник с такими длинами сторон. Если такой треугольник существует, то определите его тип (равносторонний, равнобедренный, разносторонний).

9. Имеются данные о количестве полных лет трёх призёров спартакиады. Напишите программу, выбирающую и выводящую возраст самого младшего призёра.

10. Напишите программу, определяющую, лежит ли точка А(ха, уа) на прямой у = kx + l на ней или под ней.

11. Напишите программу, которая производит обмен значений переменных х и у, если х больше у.

Какое значение имеет переменная а, если в результате выполнения условного оператора переменной с присваивается значение 3?

13. Напишите программу, вычисляющую значение функции:

Мнение эксперта

Черноволов Василий Петрович, эксперт по вопросам мобильной связи и интернета

Все сложные вопросы мы с вами решим вместе.

Задать вопрос эксперту

Подводя итог, можно выразить такие мысли для каждого подхода существует свой класс задач, который определяется по конкретным требованиям к конкретной задаче. Если вам нужна бесплатная консультация, пишите мне!

Рекурсия. Занимательные задачки / Хабр