7 Простейшие теоретико-числовые алгоритмы

7.1 Инструкции управления циклом

В задачах этого листка могут быть полезны две инструкции управляющие циклом: break и continue. Инструкция break нужна для прерывания цикла, инструкция continue используется для пропуска оставшейся части цикла и продолжения цикла со следующей итерации.

Инструкция break прерывает выполнение цикла, управление при этом немедленно передается на следующую после цикла инструкцию. Инструкция continue продолжает выполнение цикла со следующей итерации: после выполнение инструкции continue все следующие после нее в блоке цикла инструкции не выполняются, в цикле for выполняется итератор (третий параметр цикла, например, ++i), после чего проверяется условие (во всех видах циклов) и в зависимости от его значения выполняется или не выполняется тело цикла. Как правило, инструкции break и continue используются вместе с инструкцией if. После каждой из этих инструкций должна стоять точка с запятой. Пример:

     for(i=0;i<100;++i)
     {
         if(i%3==0)
             continue;
         cout<<i<<endl;
         // Выполнить еще какие-нибудь действия
     }

В этом примере переменная i в цикле принимает значения от 0 до 99. Внутри цикла проверяется условие и если i делится на 3, то оставшаяся часть цикла пропускается, и на экран будут напечатаны только те значения i, которые не делятся на 3.

Возможное применение инструкции break: в программе проверки числа на простоту прервать выполнение цикла, если найден делитель.

Упражнения

1. (A) Сложить две дроби Даны две рациональные дроби: a/b и c/d. Сложите их и результат представьте в виде несократимой дроби m/n. Программа получает на вход 4 натуральных числа a, b, c, d, не превосходящих 100. Программа должна вывести 2 натуральных числа m и n такие, что m/n=a/b+c/d и дробь m/n – несократима.
2. (B) Алгоритм Евклида. По данным натуральным числам n и m найдите их наибольший общий делитель. Числа m и n не превосходят 10⁹. Количество действий должно быть порядка log max (n;m). Указание. НОД(n,m)=НОД(n mod m,m).
3. (C) Разложение на простые множители. Напишите программу, которая по данному натуральному числу n печатает все его простые натуральные делители с учетом кратности, то есть при вводе числа 132 программа должна вывести 2 2 3 11. Время работы программы должно быть пропорционально корню из n.
4. (D) Теорема Лагранжа утверждает, что любое натуральное число можно представить в виде суммы четырех точных квадратов. По данному числу n найдите такое представление: напечатайте от 1 до 4 натуральных чисел, квадраты которых дают в сумме данное число (то есть при вводе 7 программа должна вывести 2 1 1 1).
5. (E) Представьте данное число n в виде суммы двух кубов. Например, при вводе 35 программа должна вывести 3 2. Если такое представление невозможно, выведите строку impossible.
6. (Без тестирующей системы) Совершенные числа. Натуральное число называется совершенным, если оно равно сумме всех своих делителей, меньших его самого. Например, 6 – совершенное число, поскольку 6=1+2+3. Вычислите первые пять совершенных чисел. Постарайтесь придумать наиболее эффективный алгоритм поиска совершенных чисел.
7. (F) Дружественные числа. Два числа n и m называются дружественными, если сумма делителей числа n (включая 1, но исключая само n) равна числу m и наоборот. Например, 220 и 284 – дружественные числа. По данному числу k выведите все пары дружественных чисел, каждое из которых не превосходит k. Пары необходимо выводить по одной в строке, разделяя пробелами. Каждая пара должна быть выведена только один раз (перестановка чисел новую пару не дает).
8. (G) Гипотеза Гольдбаха (недоказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел. Для данного четного n>2 напечатайте его представление в виде суммы двух простых.