《论三生原理》例:利用三生原理生成100以内素数

一、基本内容

三生原理本质上是一条简明的素数通项公式，基本内容如下：

任意不小于5的奇数p可表为：

p=3(2n+1)+2(2n+m+1)

n∈N,m={0,1,2,3,4} ,

则p为素数当且仅当同时满足以下两个条件：

①3(2n+1)与2(2n+m+1)互素；

②

<p0（n=0、m=0），或当

≥…>pi（n、m不为0）>…p2>p1>p0（i=0、1、2…，pi满足条件①②）时p与pi互素。

二、一个例图

举例列表说明利用三生原理生成100以内素数的过程方法如下：

插入的例图较小，可直接看知乎原文链接：https://zhuanlan.zhihu.com/p/443024580

三、编程代码

有赖一位知乎朋友（昵称：空白）支持提供了一段代码，即三生原理C++代码实现（时间复杂度O(n*sqrt(n)，空间复杂度O(n))）：

（知乎原文链接：https://zhuanlan.zhihu.com/p/653990991）

#include<cstdio>
#include<algorithm>
using std::__gcd;
int p[100000]={2,3},pos1=2,pos2=1;
int main(){
  for(int n=0;n<=10000;++n){
    int t=3*(2*n+1);
    for(int m=0;m<5;++m){
      int d=2*(2*n+m+1),p1=t+d;
      if(__gcd(t,d)>1)continue;
	  if(p1>p[pos2]*p[pos2]/p1){
      	if(pos2<pos1-1&&p1>p[pos2+1]*p[pos2+1]/p1)
      	  ++pos2;
		for(int i=0;i<=pos2;++i)
		  if(__gcd(p1,p[i])>1)goto notp;
		p[pos1++]=p1;
		printf("%d ",p1),_sleep(30);
	  }
	  notp:;
	}
  }
  getchar();
}