Проверка кратности

Делимость натуральных чисел. ДЕЛИТЕЛИ И КРАТНЫЕ // Простая математика [5:17]

Проверка кратности — это алгоритм определения: кратно (1) первое натуральное число второму или нет (0).

Обозначения

Введём обозначения:

a — первое натуральное число;

b — второе натуральное число;

n — результат проверки: n=1 если a кратно b, иначе 0.

Алгоритм

Входные данные: a; b.

1. c = a
2. Если c ≥ b, то c = c − b и идти к 2
3. Если с = 0, то n = 1, иначе n = 0.

Выходные данные: n.

• Заметим, что кратность можно проверить обычным делением: если число делится на второе без остатка, то оно кратно второму.

Другие алгоритмы

• наибольший общий делитель;
• наименьшее общее кратное;
• проверка кратности;
• деление по модулю;
• решето Эратосфена;
• разложение числа на множители;
• система счисления;
• метод математической индукции;
• схема примитивной рекурсии;
• виды рекурсии;
• машина Поста;
• машина Тьюринга (вероятностная);
• комбинаторные алгоритмы;
• сортировка;
• алгоритм определения мест.