因數ㄉ判斷法

引用：

debby_song2000 寫道:
請問一下ㄛ：
因數有很多ㄉ判斷方法
1.尾數判斷法
2.數字判斷法
3.間隔判斷法
可是要怎麼證明
ex：2倍ㄉ判斷法
為啥咪會有這樣ㄉ公式出來????

1.尾數是適用於2的方冪
例:2的倍數是判斷最後一位能否被2整除,原因:令一多位數ab,b為個位數,a為個位數以外的數,則ab=10a+b,而10a必為2的倍數,所以只要判斷b即可,4的倍數是判斷後兩位,因為100=4*25,以此類推

　　感謝您提出這個問題，使我們重新去深入探討．
　　對於較大的被除數與除數，例如檢查一個千位以上的數是否為37879的倍數時，在此提供神豬算法，盼能彼此切磋．
首先：
1.mod(a,b)代表a除以b所得之餘數
2.(a1,a2,.....an)*(b1,b2,....bn)=a1b1+a2b2+.....anbn

舉7的倍數而言：　
(i)mod(1,7)=1 mod(10,7)=3 mod(10^2,7)=2 mod(10^3,7)=6
　mod(10^4,7)=4　mod(10^5,7)=5　mod(10^6,7)=1..............

　將餘數1~6按位數順序組合成(5,4,6,2,3,1)
　將給定任意數以個位數起分組形成(a1,a2,a3,a4,a5,a6),(b1,b2,b3,b4,b5,b6)....,位數不夠可以補零
　例如1234567812345678可以形成(0,0,1,2,3,4),(5,6,7,8,1,2),(3,4,5,6,7,8)三組
　將各組視為向量，與餘數組(5,4,6,2,3,1)內積所得總和，檢查是否為7的倍數
　mod[(0,0,1,2,3,4)*(5,4,6,2,3,1) , 7]=2
　mod[(5,6,7,8,1,2)*(5,4,6,2,3,1) , 7]=0
　mod[(3,4,5,6,7,8)*(5,4,6,2,3,1) , 7]=4
mod(2+0+4 , 7)=6，因此
　mod(1234567812345678 , 7)=6

(ii)檢查向量(5,4,6,2,3,1)其中5+2=4+3=6+1=7　
　　mod[(5,6,7,8,1,2)*(5,4,6,2,3,1) , 7]
　　=mod[(-3,5,5,0,0,0)*(5,4,6,2,3,1) , 7]
　　=mod[(0,0,0,3,-5,-5)*(5,4,6,2,3,1) , 7]=0
亦即mod[(5,6,7,8,1,2)*(5,4,6,2,3,1) , 7]
　　=mod{[(5,6,7)-(8,1,2)]*(5,4,6) , 7}
　　=mod{[(8,1,2)-(5,6,7)]*(2,3,1)] , 7}=0
因此對於7和13的倍數判斷通常我們將三位拆成一組，求奇數位組總和與偶數位數總和之差來判斷

(iii)看似麻煩，然而，對於較大的被除數與除數，除了2,3,4,5,8,9,11較為簡單外，對於除數是較大的質數時，尋求尾數判斷法，數字判斷法，間隔判斷法尋求速解在使用電腦演算時未必能一體適用或取得速度上的優勢，使用神豬向量內積法反而省事，且對於任何較大質數均可快速求解．
　對任意數a，mod(10^n,a) 其中n=0~a-1,可以用EXCEL所附VB求出餘數1~a-1存放於陣列A(a)中
dim A(a):A(1)=1
for i=2 to a-1
k=A(i-1)*10
A(i)=k-a*int(k/a)
next
　至於將被除數以除數的位數拆成各組向量，在程式撰寫上亦很精簡，各位不妨試試．
　如此，給定一個數，即可拆成多組向量，分別與A(a)這組向量求內積總和，再判斷是否為a的倍數或求出其餘數

我想是因為我們平常用的是十進位法

數字一旦大了，不如直接除比較快吧

引用：

bubupin 寫道:

(iii)看似麻煩，然而，對於較大的被除數與除數，除了2,3,4,5,8,9,11較為簡單外，對於除數是較大的質數時，尋求尾數判斷法，數字判斷法，間隔判斷法尋求速解在使用電腦演算時未必能一體適用或取得速度上的優勢，使用神豬向量內積法反而省事，且對於任何較大質數均可快速求解．

問題是

每一次的除數都不一樣

做這個分析就有點浪費時間了吧