從666666整除7開始的算法思考

    源于一道簡單的奧數題，快速判斷666666是否能被7整除。參考的答案是前三位的666減去後三位的666，所得結果0能夠被7整除，則該數可以被7整除。

原理總結與證明

    閱讀了zhoushijingguo的新浪部落格，才發現原來整除7的方法其實衆多，這裡就選取了兩個給出自己的證明。

• 末三位相減法

      對于一個多位數，用高位的數減去末三位的數，所得的結果如果能被7整除，則該數能夠被7整除。否則，不能被7整除。

      以7位數6666666為例，高位6666減去末三位666結果為6000，不能被7整除，是以該數不能整除7。

      證明如下：

      假設 x 為任意整數,y為一至三位整數，則任意整數 I 都可以表示成x∗103+y 的形式，記 x 和y的內插補點的絕對值為 d 。由此，可得：

  I=x∗103+y(1)

  |y−x|=d(2)

      對公式(2)進行等價轉換，可得：

  y=x±d(3)

      将(3)式代入(1)式，則有：

  I=x∗103+x±d=1001x±d(4)

      分析(4)式，我們知道，1001可以整除7，是以 1001x 必然也能整除7，若 d 也能整除7，則I整除7；否則不能整除。

      即一個多位數整數能否被7整除取決于高位與末三位的內插補點是否能被7整除。

• 三位分組相減法

      可以看做是末三位相減法的拓展，但存在限制。實際手算時對于位數更多的多位數末三位相減法得到的內插補點仍然巨大，不便于計算。

      它的原理是将一個多位數按三位一節進行分組，從末向前編号1、2、3……，兩兩相鄰奇數組減去偶數組得到的內插補點絕對值數組若均能整除7，則該多位數整除7。特别注意的是，內插補點不整除7不能得出該多位數不整除7。

      例如9位數766666666，三位分組則有三組，為666，666，007，000，最低三位666編号為1，則1組減2組的絕對值為0，3組減4組(自動補0)的絕對值為7，7能整除7，是以該9位數能整除7。

      證明如下：

      假設 xi(i=0,1,2...2N+1) 為任意三位整數(不足補0),則任意整數 I 都可以表示成∑2N+1i=0xi∗103i 的形式，記 x2k 和 x2k+1(k=0,1,2...N) 的內插補點的絕對值為 dk 。由此，可得：

  I=∑i=02N+1xi∗103i(5)

  |x2k+1−x2k|=dk(6)

      對公式(6)進行等價轉換，可得：

  x2k=x2k+1±dk(7)

      将(7)式代入(5)式，則有：

  I=∑k=0Nx2k+1∗103∗(2k+1)+(x2k+1±dk)∗103∗2k=∑k=0N103∗2k∗(x2k+1∗103+x2k+1±dk)=∑k=0N103∗2k∗(1001x2k+1±dk)(8)

      分析(8)式，我們知道，1001可以整除7，是以 1001x2k+1 必然也能整除7，若 dk(k=0,1,2...N) 也能整除7，則 I 整除7；然而不能整除7時，也不能斷定I不能整除7。

算法設計

    由于三位分組相減法存在限制，故隻依據末三位相減法，對任意一個整數 I ，可以設計如下算法步驟判斷是否能被7整除：

    step 1 :判斷多位數整數I是否為6位數以内。是，轉step 2；否，轉step 4。

    step 2 :整數 d=| 高位減末三位 | 。

    step 3 :重新指派，I=d，轉step 1。

    step 4 :整數 d=| 高三位減末三位 | 。

    step 5 :若d整除7，則 I 整除7；否則I不整除7。

C語言實作

//整除7算法的C語言實作
#include <stdio.h>
#include <math.h>   
#include <time.h>   //用于計時

//末三位相減法——遞歸法
int Divide7_recursion(_int64 m){
    if(m < ){
        //判斷是否為六位數以内
        if(abs(m%-m/) % == ){
            return ;
        }
        else{
            return ;
        }
    }
    else{ 
        return Divide7_recursion(m%-m/);
    }
}

//末三位相減法——循環
int Divide7_loop(_int64 m){
    //循環降位，直到六位數以内
    for(;m>=;m = abs(m% - m/));
    if(abs(m%-m/) % == ){
        return ;
    }
    else{
        return ;
    }
}

//普通整除7算法
int Divide7_normal(_int64 m){
    if(m% == ){
        return ;
    }
    else{
        return ;
    }
}

int main(void){
    _int64 i=,count=;
    clock_t start,end;  
    start = clock(); 
    //使用十二位數進行測試
    /*末三位相減法——遞歸
    for(i=999900000000;i<999999999999;i++){
        if(Divide7_recursion(i) == 1){
            count++;
        }
    }
    */
    /*末三位相減法——循環
    for(i=999900000000;i<999999999999;i++){
        if(Divide7_loop(i) == 1){
            count++;
        } 
    }
    */
    /*普通算法
    for(i=999000;i<999999;i++){
        if(Divide7_normal(i) == 1){
            count++;
        } 
    }
    */
    end = clock();  
    printf("time=%f\n,count=%lld\n",(double)(end-start)/CLK_TCK,count); 
    return ;
}
           

總結

    從證明過程可以發現，末三位相減法的真正核心是因為1001正好可以被7整除，是以對應的是三位整數。由此，完全可以進一步拓展該方法。例如，11能夠整除11，對于整除11的數可以采用末一位相減法；1001也能夠整除13，是以末三位相減法也适用于判斷整除13的數……

    C語言代碼也僅僅隻是為了實作該算法，從彙編指令IDIV可以看出，雖然沒有用技巧性的方法，但計算機設計時已經将除法算法統一用硬體實作，而本文寫的整除算法建立在應用層，兩者速度不存在可比性。

    第一次發文，單純興趣使然，若有不足，歡迎指點。

參考部落格：

http://blog.sina.com.cn/s/blog_668e6e9d0100m6d5.html