超越欧拉筛法的质数递推算法

算法代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#define maxnyxzs 60000010
#define maxnyxfzchs 60000010
using namespace std;
long long gn(){/*get number*/
	char ch=getchar();
	long long fh=1,x=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')fh=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return (fh==1)?x:-x;
}
long long n;
long long a[maxnyxzs]={0,2},aa[maxnyxzs];
long long cfs=2/*乘法式的值*/,nc=3/*next_chengfashi 乘法式的下一个质数*/,nci=2/*next_chengfashi_i 乘法式的下一个质数的坐标*/;
long long top=2,dl=1/*duilie_long,队列长度*/ ;
long long tmp;
long long hs[maxnyxfzchs];

void shuru(){
	n=gn();
}
void clac(){
	while(1){
		//cout<<"step1"<<endl;
		while(1){
			if(a[top]==-1){
				top--; 
				continue;
			}
			if(top<nci)break;
			tmp=cfs-a[top];
			if(tmp>n)return;
			//cout<<"--------"<<endl;
			if(tmp>a[dl]){
				++dl;
				a[dl]=tmp;
			}
			top--; 
		}
		tmp=cfs-1;
		if(tmp>a[dl]){
			++dl;
			a[dl]=tmp;
		}
		tmp=cfs+1;
		if(tmp>a[dl]){
			++dl;
			a[dl]=tmp;
		}
		top=nci;
		while(1){
			if(a[top]==-1){
				top++;
				continue;
			}
			tmp=cfs+a[top];
			if(tmp>n)return;
			if(tmp>a[dl]){
				++dl;
				a[dl]=tmp;
			}
			if(tmp>cfs*a[nci]-a[dl]){
				cfs*=a[nci];
				for(long long i=nci+1;i<=dl;i++){
					if(a[i]%a[nci]==0){
						a[i]=-1;
					}
				} 
				for(long long i=nci;a[i]==-1;++i,++nci);
				nci++;
				top=dl; 
				goto step1;
			}
			top++;
		}
		step1:
		top=dl; 
	}
}
void shuchu(){
	long long top=1;
	for(long long i=1;i<=dl;++i){
		if(a[i]!=-1){
			aa[top++]=a[i];
		}
	}
	top=1;
	for(long long i=nci;i<=dl;++i){
		for(long long j=i;aa[i]*aa[j]<=n;++j){
			if(aa[i]*aa[j]==0)goto out;
			hs[top]=aa[i]*aa[j];
			top++;
		}
	}
	out:
	sort(hs+1,hs+top);
	top=1;
	for(long long i=1;i<=dl;++i){
		if(aa[i]==0)return;
		for(;aa[i]>hs[top];top++);
		if(aa[i]!=hs[top])cout<<aa[i]<<' ';
	}
}
int main(){
	shuru();
	clac();
	shuchu();
	return 0;
}

算法证明

定义非正常合数。非正常合数指的是一个自然数n，用从2开始的连续质数相乘，当乘积大于n时，用用过的除了最后一个之外的质数去除n，如果都无法整除，但n却是个合数，这时，我们就称n是非正常合数。如49（2*3*5*7=210，49÷2=24余1，49÷2=24余1，49÷3=16余1，49÷5=9余4）91，121等
定义正常合数，就是不是非正常合数的合数。如4，6，10。
定义乘法式数：用2开始连续乘i个质数，si=2×3×……×pi
Pi是第i个质数。
    
要证明用我的算法是对的，就是不多不少的算出质数和非正常合数。
也就是要证明用我的算法算出的结果一定是质数或非正常合数，并且不会漏。
先证明我的算法算出的结果一定是质数或非正常合数。
也就是证明我的算法算出的结果一定不是正常合数。
我们先证明以下定理：
如果自然数n，用n的平方根及以下的质数去除它，都不整除，那么n是质数。                                    ①
只需证明①的逆否命题：
如果n是合数，那么用n的平方根及以下的质数去除它，存在一个质数能把它整除。                                ②
不妨设②中n=pq。（p、q是非1正整数）
则p和q中必有一数小于等于n的平方根。           ③
若p小于n的平方根，③成立。
若p等于n的平方根，③成立。
若p大于n的平方根，则q小于n的平方根，③成立。
不妨设p是小于等于n的平方根的那个数，设q也一样。
若p是质数，那么p是小于等于n的平方根的质数，②成立。
若p是合数，那么将p分解质因数后，分解出来的质数一定小于p，所以小于n的平方根，②成立。
因为p是非1正整数，所以p要么是质数，要么是合数。
现在，我们回忆一下余数定理：
1.	一个数a除以另一个数b，若有余数，则a不整除b
2.	（a除以b的余数+c除以b的余数）÷b的余数等于（a+c）÷b的余数
3.	（|a除以b的余数-c除以b的余数|）÷b的余数等于（|a-c|）÷b的余数
X+si=质数或非正常合数。（x>pi，x是质数或非正常合数）④
要证明④，先把si展开：
Si=2×3×5×……×pi
而x除以上面式子中任一质数都有余数。
有余数+没余数=有余数。
  ↓      ↓     ↓
   X      si      质数或非正常合数
si -X =质数或非正常合数
有余数-没余数=有余数。
  ↓      ↓     ↓
   si       X     质数或非正常合数
成功证明用我的算法算出的结果一定是质数或非正常合数

算法时间复杂度和空间复杂度

和欧拉筛法做对比：
（假设用c++ long long类型存储，筛1亿，计算机每秒运行约1亿次（不输出，根据时间复杂度和空间复杂度估计））
欧拉筛法：时间约1s，空间6103MB左右
我的算法：时间约0.36s，空间443MB左右
时间复杂度和空间复杂度的对比（时间复杂度和空间复杂度是程序估计内存消耗和时间消耗的手段）
欧拉：时间复杂度O（n）空间复杂度O（n）
我  ：时间复杂度O（m + w×log 2 w）空间复杂度O（m + w）
m=n以下的质数个数
w=n以下非正常合数个数

算法优缺点

优点：速度快，内存省
缺点：代码长，不易编写、调试。