Представить натуральное число в виде простых сомножителей

Задача

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

Пояснение к задаче и алгоритм решения

Чтобы найти все простые сомножители натурального числа, надо его пробовать делить на простые числа, начиная с 2. Если заданное число делится без остатка, значит его делитель - это число, которое входит в состав сомножителей, из которых формируется заданное число. Как только такой сомножитель будет найден, заданное число следует на него разделить, т.е. получить новое заданное число и уже к нему заново подбирать простой делитель. Например, дано число 24. Первое натуральное число, на которое оно делится, - это 2. Значит 2 - это первый простой сомножитель. В результате деления получается 12. Далее снова находим, что 12 делится на 2. Далее 6 делится на 2. Далее 3 делится на 3. Таким образом получаем: 24 = 2 * 2 * 2 * 3.

Поскольку список простых чисел заранее неизвестен, то можно подбирать делители, увеличивая каждый следующий на 1, а не искать простые числа. Ведь если число не делится на 2, то оно не разделится и на 4, 6 и т.д.

В программах ниже есть решения с использованием оператора goto и без него. С ним решение получается короче, но с точки зрения современного программирования его использование нежелательно.

Алгоритм сводится к следующему. Пока заданное число не будет сведено к 1, делить его на натуральные числа от 2 и т.д. Как только деление будет произведено без остатка, то значит был найден простой сомножитель. Он выводится на экран, заданное число на него делится и снова начинается поиск простого делителя, начиная с 2.

Исходный код на языке программирования Pascal

label again;
var n, i: word;
begin
    readln(n);
    again:
    while n > 1 do begin
        i := 2;
        while True do
            if n mod i = 0 then begin
                n := n div i;
                write(i,' ');
                goto again;
            end
            else i := i + 1;
    end;
    writeln;
end.

Пример(ы) выполнения программы на языке Pascal

507
3 13 13

Исходный код на языке программирования C

#include <stdio.h>
main() {
    unsigned int n, i;
    scanf("%d", &n);
    again:
    while (n > 1) {
        i = 2;
        while (1) {
            if (n%i == 0) {
                n = n / i;
                printf("%d ", i);
                goto again;
            }
            else i += 1;
        }
    }
    printf("\n");
}

Пример(ы) выполнения программы на языке C

3636
2 2 3 3 101

Исходный код на языке программирования Python

n = int(input())
while n > 1:
    i = 2
    f = 0
    while 1:
        if n%i == 0:
            n = n // i
            print(i, end=' ')
            f = 1
            break
        else:
            i += 1
    if f == 1:
        continue
print()

Пример(ы) выполнения программы на языке Python

2014
2 19 53

Исходный код на языке программирования КуМир

алг простые сомножители
нач
  цел ч, п, ф
  ввод ч
  ф := 1
  нц пока ч > 1
    нц пока да
      если ф = 1 то
        п := 2
        ф := 0
      все
      если mod(ч,п) = 0 то
        ч := div(ч,п)
        вывод п, " "
        ф := 1
        выход
       иначе
        п := п + 1
      все
    кц
  кц
кон

Пример(ы) выполнения программы на языке КуМир

96
2 2 2 2 2 3

Исходный код на языке программирования Basic

input n
again:
while n > 1
        i = 2
        while 1
                if n%i = 0 then
                        n = n \ i
                        print i + " ";
                        gosub again
                endif
                i = i+1
        endwhile
endwhile

Пример(ы) выполнения программы на языке Basic

1024
2 2 2 2 2 2 2 2 2 2

Тема

Вложенные циклы

Уровень сложности

Средний

Дата публикации