3.4 Алгоритмы обработки натуральных чисел, записанных в позиционных системах счисления: разбиение записи числа на отдельные цифры,нахождение суммы и произведения цифр, нахождение максимальной (минимальной) цифры. Представление числа в виде набора простых сомножителей. Алгоритм быстрого возведения в степень. Поиск простых чисел в заданном диапазоне с помощью алгоритма «решето Эратосфена» — Подготовка к ЕГЭ/ОГЭ и сессии СПО и ВУЗы

Обработка цифр числа

Для работы с отдельными цифрами числа нужно уметь разбивать число на цифры. Это основа многих алгоритмов обработки чисел.

Основные операции с цифрами числа:

Разбиение числа на отдельные цифры
Вычисление суммы цифр числа
Вычисление произведения цифр числа
Поиск максимальной и минимальной цифры

Алгоритм разбиения числа на цифры:

                        # Разбиение числа на цифры
                        number = 12345
                        digits = []
                        
                        while number > 0:
                            digit = number % 10  # Получаем последнюю цифру
                            digits.append(digit)  # Добавляем цифру в список
                            number = number // 10 # Убираем последнюю цифру
                        
                        digits.reverse()  # Переворачиваем список
                        print(digits)     # [1, 2, 3, 4, 5]
                    

1

Шаг 1: 12345 % 10 = 5

2

Шаг 2: 1234 % 10 = 4

3

Шаг 3: 123 % 10 = 3

4

Шаг 4: 12 % 10 = 2

5

Шаг 5: 1 % 10 = 1

Сумма и произведение цифр

Сумма и произведение цифр числа — частые операции в задачах на обработку чисел.

Алгоритмы вычисления:

Сумма цифр: последовательное сложение всех цифр числа
Произведение цифр: последовательное умножение всех цифр числа
Особый случай: если число содержит 0, произведение будет равно 0

Пример: Вычисление суммы и произведения цифр

                        # Вычисление суммы цифр
                        number = 12345
                        sum_digits = 0
                        temp = number
                        
                        while temp > 0:
                            sum_digits += temp % 10
                            temp //= 10
                        
                        print(f»Сумма цифр числа {number}: {sum_digits}»)
                        
                        # Вычисление произведения цифр
                        product = 1
                        temp = number
                        
                        while temp > 0:
                            product *= temp % 10
                            temp //= 10
                        
                        print(f»Произведение цифр числа {number}: {product}»)
                    

Важно: При вычислении произведения цифр нужно инициализировать переменную-накопитель значением 1, а не 0 (так как умножение на 0 даст всегда 0).

Поиск максимальной и минимальной цифры

Для поиска максимальной и минимальной цифры в числе нужно последовательно сравнивать все цифры числа.

Алгоритм поиска:

Инициализируем переменные для хранения min и max значения
Последовательно обрабатываем каждую цифру числа
Сравниваем текущую цифру с сохраненными значениями
Обновляем min и max при необходимости

Пример: Поиск максимальной и минимальной цифры

                        # Поиск максимальной и минимальной цифры
                        number = 12345
                        temp = number
                        min_digit = 9
                        max_digit = 0
                        
                        while temp > 0:
                            digit = temp % 10
                            if digit < min_digit:
                                min_digit = digit
                            if digit > max_digit:
                                max_digit = digit
                            temp //= 10
                        
                        print(f»Минимальная цифра: {min_digit}»)
                        print(f»Максимальная цифра: {max_digit}»)
                    

Важно: При инициализации min_digit устанавливайте максимально возможное значение (9), а для max_digit — минимально возможное (0).

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

Любое натуральное число можно представить в виде произведения простых чисел — это называется разложением на простые множители.

Алгоритм разложения на простые множители:

Начинаем с первого простого числа (2)
Делим число на простое число, пока делится
Переходим к следующему простому числу
Повторяем до тех пор, пока число не станет равно 1

Пример: Разложение числа 84 на простые множители

                        # Разложение на простые множители
                        number = 84
                        factors = []
                        divisor = 2
                        
                        while number > 1:
                            while number % divisor == 0:
                                factors.append(divisor)
                                number //= divisor
                            divisor += 1
                        
                        print(factors)  # [2, 2, 3, 7]
                    

Важно: Алгоритм эффективно работает, но для очень больших чисел могут потребоваться оптимизации (проверка делителей только до √n).

Быстрое возведение в степень

Быстрое возведение в степень — алгоритм, позволяющий возводить число в степень за логарифмическое время.

Принцип работы алгоритма:

Использует свойство: aⁿ = (a²)ⁿ/² при четном n
Использует свойство: aⁿ = a × aⁿ⁻¹ при нечетном n
Сложность: O(log n) вместо O(n) у наивного алгоритма

Пример: Быстрое возведение 2¹⁰

                        # Быстрое возведение в степень
                        def fast_power(a, n):
                            result = 1
                            while n > 0:
                                if n % 2 == 1:  # Если степень нечетная
                                    result *= a
                                a *= a         # Возводим основание в квадрат
                                n //= 2        # Делим степень пополам
                            return result
                        
                        print(fast_power(2, 10))  # 1024
                    

Важно: Алгоритм быстрого возведения в степень особенно полезен при работе с большими числами и в криптографии.

Решето Эратосфена

Решето Эратосфена — эффективный алгоритм для нахождения всех простых чисел до заданного предела.

Принцип работы алгоритма:

Создаем список чисел от 2 до n
Начинаем с первого простого числа (2)
Вычеркиваем все кратные этому числу
Переходим к следующему невычеркнутому числу
Повторяем до тех пор, пока не дойдем до √n

Пример: Поиск простых чисел до 30

                        # Решето Эратосфена
                        def sieve_of_eratosthenes(n):
                            is_prime = [True] * (n + 1)
                            is_prime[0] = is_prime[1] = False
                            
                            for i in range(2, int(n**0.5) + 1):
                                if is_prime[i]:
                                    for j in range(i*i, n+1, i):
                                        is_prime[j] = False
                            
                            primes = [i for i, prime in enumerate(is_prime) if prime]
                            return primes
                        
                        print(sieve_of_eratosthenes(30))
                    

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

Простые числа до 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Важно: Решето Эратосфена — один из самых эффективных алгоритмов для поиска простых чисел в диапазоне.

Алгоритмы обработки чисел