Задача — Представить натуральное число в виде простых сомножителей
— программирование на Pascal, Си, Кумир, Basic-256, Python
Вывести на экран, из каких простых множителей состоит введенное натуральное число.
Чтобы найти все простые сомножители натурального числа, надо его пробовать делить на простые числа, начиная с 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. 507
3 13 13 Язык Си #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");
} 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() 2014
2 19 53 КуМир алг простые сомножители
нач
цел ч, п, ф
ввод ч
ф := 1
нц пока ч > 1
нц пока да
если ф = 1 то
п := 2
ф := 0
все
если mod(ч,п) = 0 то
ч := div(ч,п)
вывод п, " "
ф := 1
выход
иначе
п := п + 1
все
кц
кц
кон 96
2 2 2 2 2 3 Basic-256 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
