【专题笔记#1】质数

本文主要是介绍【专题笔记#1】质数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Prime Number Theorem

质数定理：

\([1,N]\) 中质数的个数 \(\pi(N)\sim \dfrac{N}{\log(N)}\)。

Dirichlet's theorem on arithmetic progressions

狄利克雷定理：

对于任意互质正整数对 \((r,N)\)，模 \(N\) 余 \(r\) 的质数集合相对于质数集合的密度为 \(\dfrac{1}{\varphi(N)}\)，其中 \(\varphi(N)\) 为欧拉函数。

这个定理告诉我们一个有趣的事实：若正整数 \(a,b\) 互质，则集合 \(\{a+nb \mid n \in N\}\) 中有无穷多个质数。

Dirichlet series

具有以下形式的无穷级数被称为狄利克雷级数：

\[\sum_{n=1}^{\infty}\dfrac{a_n}{n^s} \]

其中 \(s\) 是一个复数，\(a_n\) 是一个复数列。

很多狄利克雷级数都可以通过莫比乌斯反演和狄利克雷卷积得到。

Riemann zeta function

黎曼 \(\zeta\) 函数是一种特殊的狄利克雷级数。

设一复数 \(s\) 满足 \(\Re(s)\gt 1\)，则定义：

\[\zeta(s)=\sum_{n=1}^{\infty}\dfrac{1}{n^s} \]

\(s=1\) 时，右边就是我们熟悉的调和级数。

有这样一个优美的性质：

\[\dfrac{1}{\zeta(s)}=\sum_{n=1}^{\infty}\dfrac{\mu(n)}{n^s} \]

其中 \(\mu(n)\) 就是莫比乌斯函数。

Euler product

欧拉乘积：

若 \(f\) 为积性函数，则狄利克雷级数 \(\sum_n f(n)n^{-s}\) 等于欧拉乘积 \(\prod_p P(p,s)\)，其中 \(P(p,s)\) 为 \(\sum_{n=0}^{\infty}f(p^n)p^{-ns}\)。

完全形态太复杂了，当 \(f\) 为完全积性函数时，\(P(p,s)\) 是等比级数，为 \(\dfrac{1}{1-f(p)p^s}\)。

有趣的是，当 \(f(n)=1\) 时，欧拉乘积就变成了黎曼 \(\zeta\) 函数，即：

\[\sum_{n=1}^{\infty}\dfrac{1}{n^z}=\prod _p\dfrac{1}{1-p^{-z}} \]

这个等式的证明非常有趣，我们将等式左边记为式 \((0)\)，然后不断重复以下操作：

1. 将式 \((i-1)\) 乘上 \(p_i^{-1}\)，\(p_i\) 表示第 \(i\) 个质数，记为式 \((*)\)；
2. 将式 \((i-1)\) 减去式 \((*)\)，记为式 \(i\)。

容易发现这就是埃氏筛的原理，最后所有质数的倍数都被筛掉了，所以会得到这样的等式：

\[\prod_p(1-p^{-s})\zeta(s)=1^{-s} \]

把 \(\prod\) 移到右边就完事了。

现在来看一个问题：任取两个正整数互质的概率是多少？

任取两个正整数，则它们都不是第 \(k\) 个质数的倍数的概率应该是 \(1-\dfrac{1}{p_k^2}\)。

那么这两个数互质的概率就应该是 \(\prod(1-\dfrac{1}{p^2})\)，根据上面的等式，相当于 \(\dfrac{1}{\zeta(2)}\)，即 \(\dfrac{6}{\pi^2}\)。

这个问题还可以加强一下，详见 这篇博客。

这篇关于【专题笔记#1】质数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！