素数公式

2000年前的古希腊数学家埃拉特斯特尼创造了一种筛法，可以求得给定一个自然数以内的所有素数，只要在2—n内筛去不大于 ${\sqrt {n}}$ 的素数的倍数，剩下的就是素数。

素数的埃拉特斯特尼筛法公式[编辑 | 编辑源代码]

若自然数n不能被不大于 ${\sqrt {n}}$ 任何素数整除，则n是一个素数。  
    
   
  可以把上面的汉字内容等价转换成为英语字母表示：  
   
   $n=p_{1}m_{1}+a_{1}=p_{2}m_{2}+a_{2}=\dots =p_{k}m_{k}+a_{k}.$ (1)  
   
  其中  $p_{1},p_{2},\dots ,p_{k}$ 表示顺序素数2，3，5，....。 $a$ ≠0。

  若 $n<P_{k+1}^{2}$ ,则n是一个素数。  
   
  我们可以把（1）式内容等价转换同余式组表示  ：
   $n\equiv a_{1}{\pmod {p_{1}}},n\equiv a_{2}{\pmod {p_{2}}},\dots ,n\equiv a_{k}{\pmod {p_{k}}}$ （2）  
   
  由于（2）的模 $p_{1}$ , $p_{2}$ ,..., $p_{k}$  两两互素， 
  根据孙子定理(中国剩余定理）知，对于给定的 $a_{1}$ , $a_{2}$ ,..., $a_{k}$ ，（2）式在 $p_{1}$  $p_{2}$ ... $p_{k}$ 范围内有唯一解。

 　范例  
   
  k=1时， $n=2m_{1}+1$ ，解得n=3，5，7。求得了（3， $3^{2}$ ）区间的全部素数。  
   
  k=2时， $n=2m_{1}+1=3m_{2}+1$ ，解得n=7，13，19；  $n=2m_{1}+1=3m_{2}+2$ ，

解得n=5，11，17，23。

  求得了（5， $5^{2}$ ）区间的全部素数。

k=3时	$5m_{3}+1$	$5m_{3}+2$	$5m_{3}+3$	$5m_{3}+4$
$n=2m_{1}+1=3m_{2}+1=$	31	7,37	13,43	19
$n=2m_{1}+1=3m_{2}+2=$	11,41	17,47	23	29

  |}求得了（7, $7^{2}$ ）区间的全部素数。  
   
  仿此下去可以求得任意大的数以内的全部素数。并且一个不漏地求得。 
  对于所有可能的 $a_{1}$ , $a_{2}$ ,..., $a_{k}$ ，(1)和(2)式在 $p_{1}$  $p_{2}$ ... $p_{k}$ 范围内，

有（ $p_{1}-1$ ）（ $p_{2}-1$ ）( $p_{3}-1$ )...（ $p_{k}-1$ ）个解。

黎曼猜想的素数公式与埃拉托斯特尼筛法关系[编辑 | 编辑源代码]

参见《素数之恋》第100页德比希尔著。

$\zeta (s)=\sum _{n=1}^{\infty }{1 \over {n^{s}}}$

\zeta (s)={\frac {1}{1^{s}}}+{\frac {1}{2^{s}}}+{\frac {1}{3^{s}}}+{\frac {1}{4^{s}}}+\cdots

。（5）

在等号两边乘以 ${\frac {1}{2^{s}}}$ ，由幂运算规则得到。

${\frac {1}{2^{s}}}\zeta (s)={\frac {1}{2^{s}}}+{\frac {1}{4^{s}}}+{\frac {1}{6^{s}}}+{\frac {1}{8^{s}}}+\cdots$ 。（6）

 　　我们从第（6）式子减去第二个式子，在左边我有一个 $\zeta (s)$ .

又有它的 ${\frac {1}{2^{s}}}$ ,做减法得：

（ $1-{\frac {1}{2^{s}}}$ ） $\zeta (s)=1+{\frac {1}{3^{s}}}+{\frac {1}{5^{s}}}+{\frac {1}{7^{s}}}+{\frac {1}{9^{s}}}+{\frac {1}{11^{s}}}+{\frac {1}{13^{s}}}+{\frac {1}{15^{s}}}+\cdots$ 。（7）

　这个减法从那个无穷和中去掉了所有偶数项。

　　现在我们在等号两边乘以 ${\frac {1}{3^{s}}}$ ,而3是右边第一个还没有去掉的数：

${\frac {1}{3^{s}}}$ （ $1-{\frac {1}{2^{s}}}$ ） $\zeta (s)={\frac {1}{3^{s}}}+{\frac {1}{9^{s}}}+{\frac {1}{15^{s}}}+{\frac {1}{21^{s}}}+{\frac {1}{27^{s}}}+{\frac {1}{33^{s}}}+{\frac {1}{39^{s}}}+\cdots$ 。（8）

　　 　　我们再做减法得：

（ $1-{\frac {1}{3^{s}}}$ ）（ $1-{\frac {1}{2^{s}}}$ ） $\zeta (s)=1+{\frac {1}{5^{s}}}+{\frac {1}{7^{s}}}+{\frac {1}{11^{s}}}+{\frac {1}{13^{s}}}+{\frac {1}{17^{s}}}+{\frac {1}{19^{s}}}+{\frac {1}{23^{s}}}+\cdots$ 。（9）

　　　　3的所有倍数都从那个无穷和中消失了，右边还有第一个没有被去掉的数是5，如果我们两边都乘以 ${\frac {1}{5^{s}}}$ ,结果是：

${\frac {1}{5^{s}}}$ （ $1-{\frac {1}{3^{s}}}$ ）（ $1-{\frac {1}{2^{s}}}$ ） $\zeta (s)={\frac {1}{5^{s}}}+{\frac {1}{25^{s}}}+{\frac {1}{35^{s}}}+{\frac {1}{55^{s}}}+{\frac {1}{65^{s}}}+{\frac {1}{85^{s}}}+{\frac {1}{95^{s}}}+\cdots$ 。（10）

从前面那个式子减去这个式子得：

（ $1-{\frac {1}{5^{s}}}$ ）（ $1-{\frac {1}{3^{s}}}$ ）（ $1-{\frac {1}{2^{s}}}$ ） $\zeta (s)=1+{\frac {1}{7^{s}}}+{\frac {1}{11^{s}}}+{\frac {1}{13^{s}}}+{\frac {1}{17^{s}}}+{\frac {1}{19^{s}}}+{\frac {1}{23^{s}}}+{\frac {1}{29^{s}}}+\cdots$ 。（11）