Чтобы проверить, на какие числа делится данное число, есть признаки делимости.
1) Признак делимости на 2. Последняя цифра должна быть четной: 0,2,4,6,8.
2) Признак делимости на 3. Сумма цифр должна делиться на 3.
3) Признак делимости на 4. Последние две цифры образуют число, которое делится на 4.
4) Признак делимости на 5. Число должно кончаться на 0 или 5.
5) Признак делимости на 6. Число должно делиться одновременно на 2 и 3. Смотри соответствующие признаки.
6) Признак делимости на 7. Легкого для проверки признака не существует. Есть признаки, но они настолько сложные, что быстрее тупо разделить число на 7.
7) Признак делимости на 8. Последние три цифры образуют число, которое делится на 8.
8) Признак делимости на 9. Сумма цифр должна делиться на 9.
9) Признак делимости на 10. Число должно кончаться на 0.
10) Признак делимости на 11. Нужно сложить цифры через одну. Отдельно цифры на четных местах и отдельно на нечетных местах. Потом вычесть из большего меньшее. Если получится 0 или число, делящееся на 11, то исходное делится на 11.
11) Признак делимости на 12.Число должно делиться одновременно на 3 и 4. Смотри соответствующие признаки.
Дальше можно придумать аналогичные признаки делимости на 15 (3 и 5), 16 (4 последних цифры делятся на 16), 18 (2 и 9),
20 (4 и 5), 22 (2 и 11), и тому подобные произведения двух уже известных.
И еще скажу. С помощью компьютеров можно довольно легко понять, является ли данное число простым, но очень трудно разложить действительно большое число на множители.
Все современные шифры с открытым ключом основаны именно на этой трудности разложения чисел на множители.
