# 1. 概述

• 是所有数的基础（Primes are building blocks of all numbers.）
• 有特殊的性质，比如判断一个数是否质数很困难，可用于密码学

# 2. 素数判定

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
509, 521, 523, 541]


# 3. 质数生成

In computational number theory, a variety of algorithms make it possible to generate prime numbers efficiently. These are used in various applications, for example hashingpublic-key cryptography, and search of prime factors in large number.

Fig. 1: Algorithm steps for the sieve of Eratosthenes (image from Wikipedia).

# 4. 质数的分布

$$\pi(n) \sim \frac{n}{\ln(n)}$$

>>> import math
>>> 1000 / math.log(1000)                   # pi(n)，1000以内的质数约有144个
144.76482730108395

>>> import sympy
>>> len(list(sympy.primerange(1, 1000)))    # 实际上，1000以内有168个质数
168


The prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs.

$$p_n \sim n \ln n$$

>>> import math
>>> 1000 * math.log(1000)   # 第1000个素数大概在6907附近
6907.755278982137

>>> import sympy
>>> sympy.prime(1000)       # 第1000个素数是7919
7919


# 5. 质因数分解

SymPy提供两个接口返回整数分解的结果，

>>> import sympy

>>> sympy.primefactors(1000)    # Return a sorted list of n’s prime factors, ignoring multiplicity
[2, 5]

>>> sympy.factorint(1000)       # Returns a dict containing the prime factors of n as keys and their respective multiplicities as values.
{2: 3, 5: 3}

>>> pow(2, 3) * pow(5, 3)
1000


# 6. 程序库

## 6.1 SymPy

SymPy是一个符号计算的Python库，其目标是成为一个功能全面的计算机代数系统。摘抄介绍如下[4]

SymPy is a Python library for symbolic mathematics. It aims to become a full-featured computer algebra system (CAS) while keeping the code as simple as possible in order to be comprehensible and easily extensible. SymPy is written entirely in Python.

SymPy includes features ranging from basic symbolic arithmetic to calculus, algebra, discrete mathematics and quantum physics. It is capable of formatting the result of the computations as LaTeX code.

SymPy提供一些质数操作的接口，如下。

isprime(n)              # Test if n is a prime number (True) or not (False).

primerange(a, b)        # Generate a list of all prime numbers in the range [a, b).
randprime(a, b)         # Return a random prime number in the range [a, b).
primepi(n)              # Return the number of prime numbers less than or equal to n.

prime(nth)              # Return the nth prime, with the primes indexed as prime(1) = 2. The nth prime is approximately n*log(n) and can never be larger than 2**n.
prevprime(n, ith=1)     # Return the largest prime smaller than n
nextprime(n)            # Return the ith prime greater than n

sieve.primerange(a, b)  # Generate all prime numbers in the range [a, b), implemented as a dynamically growing sieve of Eratosthenes.


>>> import sympy
>>>
>>> sympy.isprime(5)
True
>>> list(sympy.primerange(0, 100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>>> sympy.randprime(0, 100)
41
>>> sympy.prime(3)
5
>>> sympy.prevprime(50)
47
>>> sympy.nextprime(50)
53
>>> list(sympy.sieve.primerange(0, 100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]


## 6.2 SageMath

SageMath is builds on top of many existing open-source packages: NumPySciPymatplotlibSymPyMaximaGAPFLINTR and many more. Access their combined power through a common, Python-based language or directly via interfaces or wrappers.

SageMath文档在Sage Documentation。关于SymPy与SageMath的区别见：StackOverflow: What is the difference between sympy and sage?

References:
[1] Wikipedia: Prime number
[2] BetterExplained: Another Look at Prime Numbers
[3] Why is the number one not prime?
[4] Wikipedia: SymPy
[5] Blogger: 求质数算法的 N 种境界[1] – 试除法和初级筛法
[6] OEIS, On-Line Encyclopedia of Integer Sequences