欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

常用算法

程序员文章站 2022-07-09 18:16:22
内容:判断质数 持续更新 # __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) ......

内容:判断质数

持续更新

常用算法
# __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

##这个倒是很简单,记住就行了,/哈哈
闰年