题目描述
线性素数筛:n 只会被 最小质因子筛掉
在筛素数时维护一个cp数组,用于判断x是否是素数,若是,则cp[x]=1
#include <iostream>
#include <cmath>
using namespace std;
const int N=1000100;
int p[N],cnt;
int st[N];
int cp[N];
void f()
{
for(int i=2;i<=N;i++)
{
if(!st[i])
{
p[++cnt]=i;
cp[i]=1;
}
for(int j=1;p[j]*i<=N;j++)
{
st[p[j]*i]=1;
//优化,如果第j个素数已经是i的约数了,就break
if(i%p[j]==0)
break;
}
}
}
int main()
{
int x;
f();
while(cin>>x,x)
{
for(int i=1;i<=cnt;i++)
{
int a=p[i];
int b=x-a;
if(cp[b]==1)
{
cout<<x<<" = "<<a<<" + "<<b<<endl;
break;
}
}
}
return 0;
}