UVA 543 Goldbach’s Conjecture Solution
Solve in C++:
#include<bits/stdc++.h>
#define M 1000009
using namespace std;
bool marked[M];
vector<int>vec;
void sieve(int n)
{
for(int i=4; i<=n; i+=2)
marked[i]=true;
for(int i=3; i*i<=n; i+=2)
{
if(marked[i]==false)
{
for(int j=i*i; j<=n; j+=i)
{
marked[j]=true;
}
}
}
vec.push_back(2);
for(int i=3; i<=n; i+=2)
{
if(marked[i]==false)
{
vec.push_back(i);
}
}
}
main()
{
int m,r,f,i;
sieve(1000009);
while(scanf("%d",&m)!=EOF)
{
int i,j,f=0;
if(m==0)
break;
for(i=0; i<(vec.size()); i++)
{
r=(m-vec[i]);
if(marked[r]==false)
{
f=1;
break;
}
if( f==1)
break;
}
if( f==1)
printf("%d = %d + %d\n",m,vec[i],r);
}
}
#include<bits/stdc++.h>
#define M 1000009
using namespace std;
bool marked[M];
vector<int>vec;
void sieve(int n)
{
for(int i=4; i<=n; i+=2)
marked[i]=true;
for(int i=3; i*i<=n; i+=2)
{
if(marked[i]==false)
{
for(int j=i*i; j<=n; j+=i)
{
marked[j]=true;
}
}
}
vec.push_back(2);
for(int i=3; i<=n; i+=2)
{
if(marked[i]==false)
{
vec.push_back(i);
}
}
}
main()
{
int m,r,f,i;
sieve(1000009);
while(scanf("%d",&m)!=EOF)
{
int i,j,f=0;
if(m==0)
break;
for(i=0; i<(vec.size()); i++)
{
r=(m-vec[i]);
if(marked[r]==false)
{
f=1;
break;
}
if( f==1)
break;
}
if( f==1)
printf("%d = %d + %d\n",m,vec[i],r);
}
}
No comments