Завдання № 33. Отримати канонічний розклад числа на прості співмножники » Pascal - основи програмування

Основи програмування на мові Pascal

 

Спонсори

Завдання № 33. Отримати канонічний розклад числа на прості співмножники

Завдання № 33. Отримати канонічний розклад числа на прості співмножники
Формулювання. Дано натуральне число n (n> 1). Отримати його канонічне розкладання на прості множники, тобто представити у вигляді добутку простих співмножників. При цьому в розкладанні допустимо вказувати множник 1. Наприклад, 264 = 2 * 2 * 2 * 3 * 11 (про-грамі допустимо видати відповідь 264 = 1 * 2 * 2 * 2 * 3 * 11).
Рішення. Дане завдання має досить гарне рішення.
З основної теореми арифметики відомо, що для будь-якого натурального числа більше 1 існує його канонічне розкладання на прості множники, причому це розкладання єдиний-ного з точністю до порядку проходження множників. Тобто, наприклад, 12 = 2 * 2 * 2 і 12 = 3 * 2 * 2 - це однакові розкладання.
    Розглянемо канонічну форму будь-якого числа на конкретному прикладі. Наприклад, 264 = 2 * 2 * 2 * 3 * 11. Яким чином можна виявити цю структуру? Щоб відповісти на це питання, згадаємо викладені в будь-якому шкільному курсі алгебри правила розподілу одночленів, предста-вив, що числа в канонічному розкладанні є змінними. Як відомо, якщо розділити вираз на змінну в деякій мірі, що міститься в цьому виразі в тій же сте-пені, воно викреслюється в її записи.
    Тобто, якщо ми розділимо 264 на 2, то в його канонічному розкладанні піде одна двійка. Потім ми можемо перевірити, чи ділиться знову вийшло приватне на 2. Відповідь буде поклади-них, але втретє поділ дасть залишок. Тоді потрібно брати для розгляду наступне натуральне число 3 - на нього приватна розділиться один раз. У підсумку, проходячи числову пряму в позитивному напрямку, ми дійдемо до числа 11, і після ділення на 11 n стане дорівнює 1, що говоритиме про необхідність закінчити процедуру.
    Чому при такому «викреслення» знайдених співмножників ми не отримаємо ділимо на складені числа? Насправді, тут все просто - будь складене число є вироблена-дением простих співмножників, менших його. У підсумку виходить, що ми викреслимо з n всі співмножники будь-якого складеного числа, поки дійдемо до нього самого в ланцюжку поділів. Напри-мер, при такому переборі n ніколи не розділиться на 4, оскільки «по дорозі» до цього числа ми ви-черкніте з n всі співмножники-двійки.


Алгоритм природною мовою:
1) Введення n;
2) Присвоєння змінної p числа 2;
3) Висновок числа n, знака рівності та одиниці для оформлення розкладу;
4) Запуск циклу з передумовою n <> 1. У циклі:
  1. Якщо m mod p = 0, то вивести на екран знак множення і змінну p, потім раз-ділити n на p, інакше збільшити значення i на 1;

 

Код:


  1. program PrimeFactors;
  2. var
  3. n, p: word;
  4. begin
  5. readln(n);
  6. p := 2;
  7. write(n, ' = 1');
  8. while n <> 1 do begin
  9. if (n mod p) = 0 then begin
  10. write(' * ', p);
  11. n := n div p
  12. end
  13. else begin
  14. inc(p)
  15. end
  16. end
  17. end.

0033.-PrimeFactors.rar [655 b] (cкачувань: 8)

скачать dle 10.4фильмы бесплатно Наступна сторінка » Завдання № 34. Сформувати число з двох ... Попередня сторінка » Завдання № 32. Перевірити монотонність...