double arrow

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

Простым является число, которое имеет только два делителя (1 и само себя). Для того чтобы определить является ли число простым, можно подсчитать количество делителей. Если делителей, кроме 1 и самого числа (number) нет, то число простое. Модифицировав алгоритм нахождения делителей числа, получаем:

kolDel:=0; // нет делителей

for delit:=2 to number div 2 do // проверяем все числа из допустимого диапазона

if number mod delit=0 then // нашли делитель

kolDel=kolDel+1; // учли делитель

// определяем «простоту» числа

if kolDel=0 then

WriteLn (’число простое’)

Else

WriteLn (’число составное’);

Нахождение наибольшего общего делителя (НОД) двух чисел

Наибольшим общим делителем (НОД) для двух целых чисел называется наибольший из их общих делителей. Например: для чисел 70 и 105 наибольший общий делитель равен 35. Одним из способов вычисления НОД двух чисел является алгоритм Евклида.

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

while number1<> number2 do // покачисла не равны

if number1> number2 then // изменяем первое число

number1:=number1-number2

else // изменяем второе число

number2:=number2-number1;

// выведем результат

WriteLn (’НОД чисел = ’, number1);

Образцы решения задачи.

Задача № 1. Определить количество и сумму цифр в числе.

Постановка задачи

Для решения данной задачи воспользуемся типовым алгоритмом выделения цифр в числе.

Входные данные.

<Число>, подлежащее обработке – number (целое).

Выходные данные.

<Сумма цифр> в числе– sum (целое).

<Количество цифр> в числе – kol (целое).

Промежуточные данные.

Последняя <Цифра> числа– temp(целое).

Алгоритм.

1. Ввести целое <Число>.

2. Обнулить <Сумма цифр> и <Количество цифр>.

3. Пока <Число> больше 0 выполняем пп. 4–7, иначе перейти на п. 8.

4. Выделить последнюю <Цифру> из числа.

5. Добавить <Цифру> числа к <Сумма цифр>.

6. Увеличить <Количество цифр> на единицу.

7. Уменьшить <Число> на один разряд.

8. Вывести <Сумма цифр> и <Количество цифр> на печать.

Текст программы.

Var

number, // число

temp, // последняя цифра

sum, // сумма цифр

kol // количество цифр

: integer;

Begin

// ввод исходных данных

WriteLn(’Введите целое число’);

ReadLn(number); // ввели число

// обработка данных

kol:=0; // количество цифр = 0

sum:=0; // сумма цифр = 0

while number<>0 do begin // пока число >0

temp:=number mod 10; // получили последнюю цифру числа

sum:=sum+temp; // добавили последнюю цифру к сумме цифр

kol:=kol+1; //увеличили количество цифр числа на еденицу

number:=number div 10 // уменьшили число на один разряд

end;

// вывод результатов

WriteLn (’Сумма цифр= ’, sum, ’Количество цифр = ’, kol)

end.

Задача № 2. Определить, является ли целое число совершенным.

Постановка задачи

Df: Совершенным называется число, которое равно сумме всех своих делителей, кроме самого числа (например: 6=1+2+3).

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

Входные данные.

<Число>, подлежащее обработке – number(целое).

Выходные данные.

<Сумма делителей> числа–sum (целое).

Промежуточные данные.

<Делитель> обрабатываемого числа–delit(целое).

Алгоритм.

1. Получить целое <Число>.

2. Присвоить начальное значение <Сумма делителей> равное 1.

3. Найти <Сумму делителей> из диапазона от 2 до половины <Числа>.

4. Если <Число> равно <Сумма делителей> тогда вывести сообщение на печать.

Текст программы

Var

number, delit, sum: integer;

Begin

// ввод исходных данных

WriteLn(’Введите целое число’);

ReadLn(number);

// вычисление суммы делителей

sum:=1; // единица всегда делитель

for delit:=2 to number div 2 do // для каждого числа от 2 до number div 2

if number mod delit =0 then // остаток от деления равен 0, т.е. это делитель числа number

sum:=sum+delit; // добавим делитель к сумме

// вывод результата

if number=sum then // число и сумма делителей равны

WriteLn (’Заданное число является совершенным’)

else // иначе

WriteLn (’Заданное число не является совершенным’)

end.

Задания для самостоятельного решения.

Вариант 1.

1. Дано натуральное число. Найти первую и последнюю цифры числа.

2. Определить количество натуральных трехзначных чисел, сумма цифр которых равна заданному числу N.

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

Вариант 2.

1. Дано натуральное число. Верно ли, что сумма цифр данного числа равна А (А вводится с клавиатуры).

2. Среди двузначных чисел найти те, сумма квадратов цифр которых делится на 13.

3. Составить программу для проверки, можно ли заданное натуральное число N представить в виде квадрата простого числа.

Вариант 3.

1. Дано натуральное число. Сколько раз данная цифра А встречается в данном числе (А вводится с клавиатуры).

2. Написать программу поиска двузначных чисел, обладающих следующим свойством: если к сумме цифр числа прибавить квадрат этой суммы, то получится снова данное число.

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

Вариант 4.

1. Дано натуральное число. Верно ли, что в данном числе сумма цифр больше В, а само число делится на В (В вводится с клавиатуры).

2. Квадраты некоторых трехзначных чисел оканчиваются тремя цифрами, которые как раз и составляют исходные числа. Написать программу поиска таких чисел.

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

Вариант 5.

1. Из данного натурального числа удалить все цифры А (А вводится с клавиатуры).

2. Среди трехзначных чисел найти те, сумма цифр которых делится на 9.

3. Составьте программу разложения натурального числа N на простые множители.

Вариант 6.

1. Дано натуральное число. Верно ли, что сумма четных цифр больше суммы нечетных цифр данного числа.

2. Квадраты некоторых двухзначных чисел оканчиваются двумя цифрами, которые как раз и составляют исходные числа. Написать программу поиска таких чисел.

3. Заданы два целых числа М, N. Определить, больше ли сумма простых делителей числа М, произведения составных делителей числа N.

Вариант 7.

1. Дано натуральное число. Верно ли, что произведение нечетных цифр данного числа меньше некоторого заданного числа.

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

3. Задано целое число N. Найти ближайшее к нему совершенное число.

Вариант 8.

1. Дано натуральное число не менее шести разрядов. Найти сумму цифр данного числа стоящих на нечетных местах.

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

3. Задано целое число N. Определить количество различных цифр числа N.

Вариант 9.

1. Найти сумму нечетных делителей натурального числа.

2. Задано целое положительное число N меньшее 32000. Написать программу, определяющую, все ли цифры числа N меньше или равны 4. Если это условие выполняется, найти сумму этих цифр.

3. Вывести на печать сто простых чисел.

Вариант 10.

1. Найти произведение четных делителей натурального числа.

2. Найти сумму целых чисел из промежутка от 1 до 200, у которых ровно 5 делителей.

3. Даны натуральные числа N, M. Получить сумму M последних цифр числа N.

Контрольные вопросы:

1. Чему будет равно значение переменной с в результате выполнения последовательности команд присваивания?

с:=12; c:=6+c div 3*2;

2. Чему будет равно значение переменной t в результате выполнения последовательности команд присваивания?

r:=7; t:=3; t:=r+t; r:=t-r; t:=t-r;

3. Сколько раз выполнится тело цикла во фрагменте алгоритма:

b:=true; x:=64;

while b do begin

b:=(x>=4);

x:=x div 6+2

end;

4. Сколько раз выполнится тело цикла во фрагменте алгоритма:

q:=27; p:=36;

while q div 5= p div 7 do begin

q:=q+2; p:=p+3

end;

5. Укажите, чему будет равно значение v после выполнения фрагмента алгоритма, если вводится целое значение n, равное 125...

с:=100; v:=0;

while n>0 do begin

v:=v+n div c;

n:=n mod c;

c:=с div 10

end;

6. Вычислите результат выполнения фрагмента алгоритма:

n:=10;

s:=0;

for i:=1 to n div 2 do

s:=s+ n mod i;

7. Вычислите результат выполнения фрагмента алгоритма:

n:=19;

s:=0;

for i:= 2 to n mod 7 do begin

s:=s+ n div i;

n:= n div 2;

end;

8. Какую операцию целочисленного деления необходимо использовать для получения цифры числа?

9. Почему целесообразнее выделять цифры из числа справа налево, а не слева направо?

10. Какой алгоритм необходимо применить, если все-таки цифры из заданного числа выделять слева направо?



Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: