常用演算法

內容：判斷質數

持續更新

# __author: _nbloser
# date: 2018/2/4

import math
def is_prime(number):
    num_sqrt = int(math.sqrt(number))
    for i in range(2, num_sqrt + 1):
        if number % num_sqrt == 0:
            return False
    return True

if __name__ == '__main__':
    n = int(input('輸入要判斷的數：'))
    print(is_prime(n))

# __author: _nbloser
# date: 2018/3/2

### 求a^m mod n  。 返回的d為答案，比如  2^3  mod 5 = 3 ,則返回3
def mod(a, m, n):
    temp = m
    c = 0
    d = 1
    k = len(bin(a).replace('0b', ''))
    b = [0 for x in range(k)]  # 創建長度為k的數組/  a = [0]*10 後面這個快
    for i in range(k):
        if (0 == temp % 2):
            b[i] = 0
        else:
            b[i] = 1
        temp = temp / 2
    for i in range(k-1):
        c = c*2
        d = (d*d) % n
        if 1 == b[i]:
            c = c+1
            d = (d*a)%n
    return d

"""這個演算法是我在學密碼學的時候要用到，開始是c語言，後面我用python比較好用，我就改成python版本了，c語言版本在下麵
//求 a 的 m 次方模 n 演算法
int mod(int a, int m , int n ){
    int c = 0;
    int d = 1;
    
    //算 m 有多少二進位位，即求 k 
    int k = 1;
    int temp = 2;
    while(temp < m){
        temp = temp * 2;
        k++;
    }
    
    //把 m 放入數組 b[k]中 
    int b[k];
    int i;
    temp = m;
    for( i = 0; i < k; i++ ){
        if( 0 == temp%2){
            b[i] = 0;
        }
        else{
            b[i] = 1;
        }
        temp = temp/2;
    }


    for( i = k-1; i >= 0; i--){
        c = c * 2;
        d = (d*d) % n;
        if( 1==b[i] ){
            c = c + 1;
            d = (d*a)%n;
        }
    }
    return d;
} 
"""

# __author: _nbloser
# date: 2018/3/3

def is_leapyear(year):
    if year % 4 == 0 and year % 100 != 0 or year % 400 == 0:
        return True
    else:
        return False

##這個倒是很簡單，記住就行了，/哈哈