当前位置:网站首页>数论基础及其代码实现

数论基础及其代码实现

2022-07-01 12:35:00 51CTO


文章目录

欧几里得

      
      
# 欧几里得 求最大公约数
# 内置函数
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
数论基础及其代码实现_质因子


原网站

版权声明
本文为[51CTO]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_14608932/5434369