素數公式

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）