Делимость чисел

1. Задано натуральное число А. Вычислить сумму цифр числа.

Пример ввода: 71203

Пример вывода: 13

s:=0;

while a>0 do

begin

cif:=a mod 10;

s:=s+cif;

a:=a div 10;

end;

writeln(‘сумма =’, s);

2. Задано натуральное число А. Получить число B являющееся перевертышем числа А.

Пример ввода: 71203

Пример вывода: 30217

b:=0;

while a>0 do

begin

cif:=a mod 10;

b:=b*10+cif;

a:=a div 10;

end;

writeln(‘b =’, b);

3. Задано число А (1<A<1 000 000 000). Получите число B, поменяв местами первую и последнюю цифру числа A.

Пример ввода: 71203

Пример вывода: 31207

4. Задано число А (1<A<1 000 000 000). Получите число B, добавив вначале и в конце числа цифру 9.

Пример ввода: 71203

Пример вывода: 9712039

5. На заданном интервале натуральных чисел от N до M найти все палиндромы (палиндромом будем называть число, если его запись читается одинаково с начала и с конца). Данные корректны (0<N<M).

Пример ввода: 80 130

Пример вывода: 88 99 101 111 121

kl:=0;

for i:=N to M do

begin

a:=i;

b:=0;

while a>0 do

begin

cif:=a mod 10;

b:=b*10+cif;

a:=a div 10;

end;

if b=i then

begin

kl:=1;

write(i, ‘ ’);

end;

if kl=0 then writeln(‘палиндромов нет’);

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

6. Задано натуральное число А. Найдите все делители этого числа.

Пример ввода: 60

Пример вывода: 1 2 3 4 5 6 10 12 15 20 30 60

I способ

Просматриваем все натуральные числа от 1 до A, и выдаём на экран те из них на которые А делится без остатка.

readln (a);

for i:=1 to a do

if a mod i = 0 then write(i, ‘ ’);

Проанализируем данный способ. При А равном например 1 028 764 800 будет выполнено соответственно более миллиарда операций.

II способ

Ускорим данный алгоритм. Понятно, что после половины числа (514 382 400) делителей быть не может. Т.е. искать делители на промежутке от А/2 до А бесполезно. Такое простое усовершенствование даёт экономию по времени в 2 раза.

readln (a);

for i:=1 to (a div 2) do

if a mod i = 0 then write(i, ‘ ’);

write(a);

III способ

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

Например для числа 60: 1 и 60, 2 и 30, 3 и 20, 4 и 15, 5 и 12, 6 и 10.

Причём ясно, что числа первой группы меньше sqrt(А), а числа второй группы больше sqrt(А).

Т.о. достаточно просмотреть все натуральные числа от 1 до sqrt(А) и выдать на экран те из них, на которые А делится без остатка (это будут числа первой группы) и частное от деления (это будут числа второй группы)

readln (a); k:=round(sqrt(a));

for i:=1 to k do

if a mod i = 0 then write(i, ‘ ’,a div i, ‘ ’);

Проанализируем данный способ.

Для числа А порядка 109 данный способ будет работать в 33 000 раз быстрее чем первый.

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

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

IV способ

readln (a); k:=round(sqrt(a));

for i:=1 to k do

if a mod i = 0 then write(i, ‘ ’);

for i:=1 to k do

if a mod i = 0 then write(a div i, ‘ ’);

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

7. Дано натуральное число А. Является ли оно простым.

Пример ввода: 60 13

Пример вывода: составное простое

Число называется простым, если оно имеет два делителя: 1 и самого себя.

Если делителей больше двух, то число называется составным.

Число 1 не относится не к простым не к составным.

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

I cпособ

Он будет заключаться в том, что заданное натуральное число делим на все числа от 1 до A и подсчитываем количество делителей. Если количество делителей равно 2, то число является простым, иначе составным.

readln(a);

kol:=0;

for i:=1 to a do

if a mod i=0 then inc(kol);

if kol=2 then writeln('простое') else writeln ('не простое');

II способ

Можно ускорить предыдущий алгоритм в два раза, если учесть, что у натурального числа A между A/2 и A делителей нет.

readln(a);

kol:=0; k:=a div 2;

for i:=2 to k do

if a mod i=0 then kol:=kol+1;

if kol=0 then writeln('простое') else writeln ('не простое');

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

III способ

Если у натурального числа A до корня квадратного нет делителей, то делителей не будет и после корня квадратного.

readln(a);

kol:=0; k:=round(sqrt(a))+1;

for i:=2 to k do

if a mod i=0 then kol:=kol+1;

if kol=0 then writeln('простое') else writeln ('не простое');

Данный алгоритм работает быстро при любых значениях n. Но и его можно ускорить.

IV способ

Остановим алгоритм, если количество делителей перестанет быть равным 0.

readln(a);

kol:=0; k:=round(sqrt(a))+1;

i:=2;

while (i<=k) and (kol=0) do

begin

if a mod i=0 then kol:=kol+1;

i:=i+1;

end;

if kol=0 then writeln('простое') else writeln ('не простое');

Vспособ

Будем проверять делится ли число на 2, а далее только на нечётные числа.

readln(a);

kol:=0; k:=round(sqrt(a))+1;

if a mod 2=0 then kol:=kol+1;

i:=3;

while (i<=k) and (kol=0) do

begin

if a mod i=0 then kol:=kol+1;

i:=i+2;

end;

if kol=0 then writeln('простое') else writeln ('не простое');

8. На диапазоне чисел от M до N (1<M<N - натуральные) найти все простые числа.

Пример ввода: 13 40

Пример вывода: 13 17 19 23 29 31 37

Данную задачу, как и задачу 5 можно совершенствовать.

Перебираем все натуральные числа от M до N и каждое число проверяем, является ли оно простым (используем V способ задачи 6)

readln (m, n);

for j:=m to n do

begin

kol:=0; k:=round(sqrt(j))+1;

if j mod 2=0 then kol:=kol+1;

i:=3;

while (i<=k) and (kol=0) do

begin

if a mod i=0 then kol:=kol+1;

i:=i+2;

end;

if kol=0 then write(j, ‘ ’);

end;

9. На диапазоне чисел от M до N (1<M<N - натуральные) найти все простые числа (используя “Решето Эратосфена”)

var n,m,i,j:longint;

f1,f2:text;

a:array[1..1000000] of byte;

Begin

assign(f1,'input.txt'); assign(f2,'output.txt');

reset(f1); rewrite(f2);

readln(f1,m,n);

for i:=1 to n do

a[i]:=1;

a[1]:=0;

for i:=2 to (round(sqrt(n))) do

begin

j:=i*i;

while (j<=n)and(a[i]<>0) do

begin

a[j]:=0;

j:=j+i;

end;

for i:=m to n do

if a[i]=1 then write(f2,i,' ');

close(f1); close(f2);

End.

10. Задано натуральное число А. Разложите это число на простые множители.

Пример ввода: 180

Пример вывода: 2 2 3 3 5

readln (a);

i:=2;

while a>1do

if a mod i=0 then

begin write (i,‘ ’); a:=a div i; end

else

inc(i);

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

1. Задано натуральное число N. Подсчитать сумму делителей числа N.

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

3. Найти 100 первых простых чисел.

4. Дано четное число n>2. Проверить для этого числа гипотезу Гольдбаха. Эта гипотеза (по сегодняшний день не опровергнутая и полностью не доказанная) заключается в том, что каждое четное n, большее двух, представляется в виде суммы двух простых чисел.

5. Дано натуральное число n. Выяснить, имеются ли среди n, n+1, ..., 2n близнецы, т.е. простые числа, разность между которыми равна двум.

6. Проверить теорему П. Л. Чебышева, что между двумя натуральными числами n и 2n имеется, по крайней мере, одно простое число.

7. Найти все простые числа меньшие заданного числа n, являющиеся числами Мерсена. Числа Мерсена соответствуют формуле (2k-1, k - натуральное).

8. Учитывая, что простыми числами, большими 3, могут быть только числа вида: 6n+1 и 6n-1, составить программу нахождения всех простых чисел больших a и меньших b (a, b – заданы).

9. Задано натуральное число n. Подсчитать количество пар – близнецов меньших n.

10. Даны натуральные числа a, b (a<=b). Получить все пары чисел–близнецов больших a и меньших b.

11. Исследовать плотность вхождения пар - близнецов в первом миллионе, подсчитывая по тысячам, десяткам тысяч, сотням тысяч. Сделать вывод.

Олимпиадные задания

1. Сосчитать количество единиц в двоичной записи числа N.

2. Вводится N. Необходимо найти, на сколько нулей оканчивается N!=1*2*3*...*N.

3. Число вводится своим двоичным представлением (длина числа не превышает 10000 двоичных разрядов). Необходимо определить делится ли число на 15.

4. Задано натуральное число N, содержащее до 100 цифр. Делится ли данное число на

a) 3

b) 6

c) 7

d) 9

e) 11

f) 12.