当前位置：网站首页>Fundamentals of number theory and its code implementation

Fundamentals of number theory and its code implementation

2022-07-01 12:41:00 【51CTO】

List of articles

Euclid
Minimum common multiple
Sieve to find the prime number （ Prime sieve ）
Basic theorem of arithmetic
The permutation number of multiple sets

Euclid

       
       #  Euclid   Find the greatest common divisor 
       
       #  Built in functions 
       
       a,
       
       b 
       
       = 
       
       1,
       
       5
       
       import 
       
       math
       
       res 
       
       = 
       
       math.
       
       gcd(
       
       a,
       
       b)
       
       print(
       
       res)
       
       #  Write it yourself 
       
       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.

Minimum common multiple

Sieve to find the prime number （ Prime sieve ）

       
       #  Sieve to find prime number  O(N)
       
       #  You can get 2-n The prime number in  1 Not prime 
       
       N 
       
       = 
       
       100010
       
       primes
       
       = [
       
       0 
       
       for 
       
       i 
       
       in 
       
       range(
       
       N)] 
       
       #  Existential prime 
       
       st 
       
       = [
       
       0 
       
       for 
       
       i 
       
       in 
       
       range(
       
       N)] 
       
       #  Has the current number been screened  0 Represents not being screened   It shows that the number is a prime number   Otherwise, it's not 
       
       def 
       
       get_primes(
       
       n):
       
       cnt 
       
       = 
       
       0 
       
       #  Prime subscript 
       
       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.

Basic theorem of arithmetic

Every Greater than 1 The natural number of , If it's not itself, it's a prime number , It can be written as 2 More than one Prime number Product of , And after these qualitative factors are arranged in size , There is only one way to write .
for example 6 It can be written. 2 * 3