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

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

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

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

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

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

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.

507

3 13 13

#include 

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");

}

3636

2 2 3 3 101 

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()

2014

2 19 53

алг простые сомножители 

нач

  цел ч, п, ф

  ввод ч

  ф := 1

  нц пока ч > 1 

    нц пока да

      если ф = 1 то

        п := 2

        ф := 0

      все

      если mod(ч,п) = 0 то 

        ч := div(ч,п)

        вывод п, " "

        ф := 1

        выход

       иначе

        п := п + 1

      все

    кц

  кц

кон

96

2 2 2 2 2 3

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

1024

2 2 2 2 2 2 2 2 2 2