Статья Автор: Корельская Елена Юрьевна

Теория

На уроках математики в 5-6 классах вы уже научились раскладывать число на простые сомножители. Например, 1980 = 2 * 2 * 3 * 3 * 5 * 11.
Напомним, что натуральное число, большее 1, называется простым, если оно имеет только два делителя: единицу и само число. Первые 7 простых чисел: 2, 3, 5, 7, 11, 13, 17.
Основная теорема арифметики утверждает, что любое натуральное число можно представить в виде произведения простых делителей, взятых в натуральных степенях, причём это разложение единственно с точностью до порядка следования множителей.
Разложение натурального числа на простые множители применяется в решении ряда задач математики: нахождение наибольшего общего делителя, наименьшего общего кратного, проверка делимости числа.
Сегодня мы научимся раскладывать на множители с помощью программ, написанных на языке программирования Python.
Для начала решим задачу о количестве вхождений конкретного множителя «2» в разложение числа.

ввод числа n
счетчик вхождения «2» = 0
пока число делится на 2
увеличить счетчик на 1
число n поделить нацело на 2
вывод счетчика

Число n	Число делится на 2	Счетчик
120	+	1
60	+	2
30	+	3
15	-

На основе предыдущей задачи и на примере при n=120 и n = 128, сделайте вывод, когда можно утверждать, что натуральное число является степенью двойки.

Число n	Число делится на 2	Счетчик
120	+	1
60	+	2
30	+	3
15	-

Число n	Число делится на 2	Счетчик
128	+	1
64	+	2
32	+	3
16	+	4
8	+	5
4	+	6
2	+	7
1	-

Действительно, если при цикличном делении на 2 получается «1», то число – некоторая натуральная степень числа 2. Если не «1», то не степень двойки.
Решим задачу о разложении натурального числа на простые сомножители. Идея решения состоит в следующем: будем последовательно перебирать возможные делители d числа, начиная с двойки. Если d – делитель числа n, выводим делитель, а число уменьшаем в d раз. Если же d – не делитель, берем следующее число в качестве потенциального делителя.
Таким образом, в качестве делителя будем перебирать последовательно числа: 2, 3, 4, 5, 6 и т.д. Но ведь часть чисел не являются простыми, а разложить нужно именно на простые множители. Оказывается, что, когда происходило деление на 2 несколько раз, число уже разделили на все степени 2. Потом делили на 3 – поделили на все степени 3 и произведение степеней 2 и 3 (на 6 в том числе). Таким образом, хоть мы и проверяем делимость на составные числа, но таких делителей у числа n не будет.
Ввод числа n
d = 2
пока n не 1
      если n делится нацело на d
            вывести d
            n нацело разделить на d
      иначе
            d увеличить на 1

n	d	Вывод на экран
1980	2	2
990	2	2
495	3	3
165	3	3
55	4
55	5	5
11	6
11	7
11	8
11	9
11	10
11	11	11
1

Для числа n вывести все простые делители в разложении и их количество.
Ввод числа n
d = 2
пока n не 1
      если n делится нацело на d
            счетчик = 0
            пока n делится на d
                  n нацело разделить на d
                  счетчик увеличить на 1
            вывести d и счетчик

      иначе
            d увеличить на 1

Чтобы оставить комментарий нужна авторизация

Печать