数论基础及其代码实现

文章目录

• ​ ​欧几里得​​
• ​ ​最小公倍数​​
• ​ ​筛法求质数（质数筛）​​
• ​ ​算术基本定理​​
• ​ ​多重集的排列数​​

欧几里得

登录后复制

      
      

       
       # 欧几里得 求最大公约数
       
       

       
       # 内置函数
       
       

       
       a,
       
       b 
       
       = 
       
       1,
       
       5
       
       

       
       import 
       
       math
       
       

       
       res 
       
       = 
       
       math.
       
       gcd(
       
       a,
       
       b)
       
       

       
       print(
       
       res)
       
       

       
       

       
       # 自己写
       
       

       
       def 
       
       gcd(
       
       a,
       
       b):
       
       
    
       
       return 
       
       gcd(
       
       b,
       
       a
       
       %
       
       b) 
       
       if 
       
       b 
       
       else 
       
       a
       
       

       
       print(
       
       gcd(
       
       a,
       
       b))
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
      
      

最小公倍数

登录后复制

      
      

       
       import 
       
       math
       
       

       
       math.
       
       lcm(
       
       2,
       
       6)
      
      
      
      

       
       
1.
       
       
2.
      
      

筛法求质数（质数筛）

登录后复制

      
      

       
       # 筛法求素数 O(N)
       
       

       
       # 可以得到2-n内的质数 1不是质数
       
       

       
       N 
       
       = 
       
       100010
       
       

       
       primes
       
       = [
       
       0 
       
       for 
       
       i 
       
       in 
       
       range(
       
       N)] 
       
       # 存素数
       
       

       
       st 
       
       = [
       
       0 
       
       for 
       
       i 
       
       in 
       
       range(
       
       N)] 
       
       # 当前数有没有被筛过 0代表没有被筛过 说明该数是质数 否则不是
       
       

       
       

       
       def 
       
       get_primes(
       
       n):
       
       
    
       
       cnt 
       
       = 
       
       0 
       
       # 质数下标
       
       
    
       
       for 
       
       i 
       
       in 
       
       range(
       
       2,
       
       n
       
       +
       
       1):
       
       
        
       
       if 
       
       not 
       
       st[
       
       i]:
       
       
            
       
       primes[
       
       cnt] 
       
       = 
       
       i
       
       
            
       
       cnt 
       
       += 
       
       1
       
       
        
       
       j 
       
       = 
       
       0
       
       
        
       
       while 
       
       primes[
       
       j] 
       
       * 
       
       i 
       
       <= 
       
       n:
       
       
            
       
       st[
       
       primes[
       
       j] 
       
       * 
       
       i] 
       
       = 
       
       1
       
       
            
       
       if 
       
       i 
       
       % 
       
       primes[
       
       j] 
       
       == 
       
       0:
       
       
                
       
       break
       
       
            
       
       j 
       
       += 
       
       1
       
       

       
       

       
       get_primes(
       
       100000)
       
       

       
       for 
       
       i 
       
       in 
       
       range(
       
       20):
       
       
    
       
       print(
       
       primes[
       
       i])
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
      
      

算术基本定理

每个大于1的自然数，若不是本身就是质数，就是可写为2个以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。
例如 6 可以写成 2 * 3

多重集的排列数

比如1 1 2 2 3的排列数是多少
5! / 2! 2!1！ = 10