Обоснование и алгоритм разложения на простые множители

1. Метод пробных делений

2. Метод пробных делений

3. Шаги алгоритма

1. Пусть n — число, которое нужно разложить на
простые множители.
2. Начинаем с минимального простого числа p = 2.
3. Пока n > 1:
1. Если n делится на p без остатка (n mod p=0):
1. Запишем p как множитель.
2. Разделим n на p ( n = n/p ).
2. Иначе:
1. Увеличим p на 1 ( p = p+1 ).
4. Конец алгоритма, когда n = 1.

4. Обоснование алгоритма

5. Обоснование алгоритма

1.
2.
3.

6. Обоснование алгоритма

1.
2.

7. Обоснование алгоритма

8. Сложность алгоритма

9. Программа