Предмет: Информатика, автор: Belerefon

решите задачу на питоне
Python 3.1

Дано натуральное число N. Требуется представить его в виде суммы двух натуральных чисел A и B таких, что НОД (наибольший общий делитель) чисел A и B — максимален.

Ограничение по времени выполнения программы - 1 секунда, ограничение по используемой памяти - 64 мегабайта.

Входные данные
Во входном файле записано натуральное число N (2≤N≤109)

Выходные данные
В выходной файл выведите два искомых числа A и B. Если решений несколько, выведите любое из них.

Примеры
входные данные
15
выходные данные
5 10
входные данные
16
выходные данные
8 8

Ответы

Автор ответа: PozziBrj
0

Ответ:

Объяснение:

Если A, B имеют общий делитель d, то и A + B делится на d. Отсюда идея: найдем наибольший делитель N, меньший N, и представим всё в виде d + (N - d). d будем искать так: найдём наименьший делитель q, не равный 1 (если число составное, он не больше корня из N), тогда d = N/q.

var

 q, d, n: longint;

 isfound: boolean;

begin

 readln(n);

 isfound := false;

 for q := 2 to trunc(sqrt(n)) + 1 do

   if n mod q = 0 then

   begin

     d := n div q;

     write(d, ' ', n - d);

     isfound := true;

     break;

   end;

 if not isfound then

   write(1, ' ', n - 1);

end


Belerefon: нужно было на питоне мне пришлось с паскаля переводить
Похожие вопросы
Предмет: Английский язык, автор: dedinsided536
Предмет: Алгебра, автор: alexc1984