Проверка делимости на 6 , Самая быстрая

[arcsupport]

Как ОЧЕНЬ быстро проверить, делится ли число на 6 (шесть)?

[MIF]

Число делится на 6, если оно делится на 2 (четное) и на 3 (сумма всех цифр кратна 3).

[Flex Ferrum]

Цитата arcsupport @ 15.06.06, 11:42

Как ОЧЕНЬ быстро проверить, делится ли число на 6 (шесть)?

Четное и сумма цифр делится на три.

[arcsupport]

Это я и сам знаю. Просто слышал о том, что есть какие-то спец
признаки делимости

[BlackRabbit]

C/C++:

if(!Number%6)
   printf("\nЧисло делится на 6\n");
else
   printf("\nЧисло не делится на 6\n");

Pascal:

if (Number mod 6) = false then
   writeln('Число делится на 6');
else
   writeln('Число не делится на 6');

Вроде так, хотя я такой ламер, что могу неправильно понять задание или что-то не так написать

Сообщение отредактировано: BlackRabbit - 15.06.06, 12:49

[p_kolya]

Число делится на 6, если делится на каждое из 3 вподряд идущих числа. Т.е. N делится на 6, если оно делится на m, m+1, m+2, (или m*(m+1)*(m+2)) где m целое. Это изходя из того, что одно из этих трех чисел четное и одно делится на 3 (т.е. каждое третье число делится на 3 ).

[LuckLess]

Цитата p_kolya @ 15.06.06, 13:51

Число делится на 6, если делится на каждое из 3 вподряд идущих числа. Т.е. N делится на 6, если оно делится на m, m+1, m+2, (или m*(m+1)*(m+2)) где m целое. Это изходя из того, что одно из этих трех чисел четное и одно делится на 3 (т.е. каждое третье число делится на 3 ).

числа 4,5,6 .. 21 делиться только на 3..

[Romtek]

Цитата arcsupport @ 15.06.06, 11:42

Как ОЧЕНЬ быстро проверить, делится ли число на 6 (шесть)?

Отнимай от N цифру 6 в цикле до тех пор, пока число не станет меньше либо равным 6. Если равно 0, то делится без остатка.
Сомневаюсь, что получится быстрее % 6 (mod 6) вручную, чем компилятором.

[Flex Ferrum]

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

[Змей]

на VB:

k=clng(x/6)
if k*6=x then
'делится
else
'не делится
endif

clng(x/6)-преобразование в Long. Дробная часть отбрасывается. аналогично int(x), но вроде немного побыстрее работает.

[p_kolya]

Цитата LuckLess @ 15.06.06, 13:54

числа 4,5,6 .. 21 делиться только на 3..

Ты наверно (или я плохо объяснил) не так понял меня. Вот есть число X. Если оно делится на 4, 5, 6, то оно делится на 6... ну тут очевидно. Или если X делится на 20 21 22, то оно делится на 6 и аналогично, например если оно делится на 123 124 125... то делится на 6, т.к. 124 четное, 123 кратно 3... и.т.п.

[KAV_Invariant]

Еще один способ, правда, не для быстроты реализации, а просто так:
число делится на K, если его сумма цифр делится на K в K+1 - ричной системе счисления
Поэтому-то и есть признак делимости на 9, потому что у нас 10-ричная система .

[MIF]

Цитата KAV @ 15.06.06, 16:36

Еще один способ, правда, не для быстроты реализации, а просто так:
число делится на K, если его сумма цифр делится на K в K+1 - ричной системе счисления

Ну, тогда еще один способ:
Число делится на К, если в К-ричной системе счисления в младшем разряде - 0.

[leo]

Romtek
> "Сомневаюсь, что получится быстрее % 6 (mod 6) вручную, чем компилятором"

А я сомневаюсь в том, что компилятор в данном случае использует что-либо кроме банального и тормозного деления
Хотя методы быстрого деления и умножения на константы хорошо известны. К примеру определение остатка от деления на 6 можно записать на асме так (для положительных чисел)

function Mod6(x:integer):integer; register;
asm //число x в eax
  mov ecx,eax
  mov edx,$AAAAAAAB   //0AAAAAAABh = round((2^34)/6)
  mul edx             //edx:eax = x*round((2^34)/6)
  shr edx,2           //эквивалентно * 2^34 => в edx частное
  mov eax,ecx        
  lea edx,[edx+edx*2] //*3
  add edx,edx         //*2
  sub eax,edx         //остаток
end;

[arcsupport]

Дальше сам буду разбираться