число делится на 17?

Question

Учитывая большое положительное число не более 1000 цифр.Вы должны выяснить, делится ли это число на 17 или нет.Я знаю алгоритм, который говорит, умножьте последнюю цифру на 5 и вычтите из оставшегося числа, если полученное число делится на 17, то число делится на 17. Есть ли более эффективный метод?

Answer 1

Что вы можете сделать, это перебирать цифры, отслеживая текущее значение по модулю 17. Когда вы достигнете конца, если текущее значение по модулю 17 равно нулю тогда это кратное 17; в противном случае нет.

Например, если ваш номер "12345" (я предполагаю, что этот номер хранится в десятичной строке?), То шаги:

• начать с 0
• (0 * 10 + 1) mod 17 & rarr; 1
• (1 * 10 + 2) mod 17 & rarr; 12
• (12 * 10 + 3) mod 17 & rarr; 4
• (4 * 10 + 4) mod 17 & rarr; 10
• (10 * 10 + 5) mod 17 & rarr; 3

поэтому 12345 mod 17 равно 3: 12345 не делится на 17.

(Конечно, с 12345 вы могли бы просто написать 12345 mod 17 для начала, но с огромными числами, вышеуказанный подход позволяет нам обрабатывать чуть-чуть за раз, что удобно, потому что это означает, что все наши числа достаточно малы, чтобы поместиться в 32- или 64-разрядные целые числа процессора.)

Answer 2

Другой вариант.10 ⁸ - это -1 мод 17.

Итак, возьмите первые 8 цифр, преобразуйте их в число и% 17, чтобы получить оставшийся мод 17. Затем повторите со следующими 8 цифрами, кромечто вы вычтите число на этот раз.Затем добавьте следующие 8 цифр и т. Д.

Это приведет к меньшему количеству преобразований строк-> чисел и уменьшению количества операций мода 17.

Answer 3

Учитывая, что мы говорим о компьютерных программах, выполнение 1000 итераций простого алгоритма довольно быстро.