I was solving [D. Dima and Lisa](http://https://mirror.codeforces.com/contest/584/problem/D) and I was unable to solve the question by myself after trying for an hour. I knew about Goldbach's Conjecture so I had an idea as to how to solve the problem to some extent leaving behind to find last two primes (for n<=10^9) (after setting first one to 3 among the three primes). (For n>9)↵
↵
I saw the submissions of some coders and they solved the question exactly as follows for the last two prime numbers.↵
↵
//the function for prime checking↵
↵
↵
~~~~~↵
bool isPrime(int x)↵
{↵
for(int i=2;i*i<=x;i+=1)↵
{↵
if(x%i==0)↵
{↵
return false;↵
}↵
}↵
return true;↵
}↵
int main()↵
{↵
int n;↵
cin>>n;↵
if(n==3)↵
{↵
cout<<1<<endl;↵
cout<<3<<endl;↵
}↵
else if(n==5)↵
{↵
cout<<1<<endl;↵
cout<<5<<endl;↵
}↵
else if(n==7)↵
{↵
cout<<1<<endl;↵
cout<<7<<endl;↵
}↵
else if(n==9)↵
{↵
cout<<3<<endl;↵
cout<<3<<" "<<3<<" "<<3<<endl;↵
}↵
else↵
{↵
cout<<3<<endl;↵
cout<<3<<" ";↵
for(int i=3;2*i+3<=n;i+=2)↵
{↵
if(isPrime(i)&&isPrime(n-3-i))↵
{↵
cout<<i<<" "<<n-3-i<<endl;↵
break;↵
}↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
↵
The code seems to run with an worst case complexity of O(sqrt(n)*n) and in the given question n<=10^9 and still the submissions gets an AC in just **31ms**.↵
↵
Here you go with the solution.↵
[My Submission](https://mirror.codeforces.com/contest/584/submission/92408590)↵
↵
How is it possible? If I am wrong at finding out the complexity please help and tell how this works?
↵
I saw the submissions of some coders and they solved the question exactly as follows for the last two prime numbers.↵
↵
//the function for prime checking↵
↵
↵
~~~~~↵
bool isPrime(int x)↵
{↵
for(int i=2;i*i<=x;i+=1)↵
{↵
if(x%i==0)↵
{↵
return false;↵
}↵
}↵
return true;↵
}↵
int main()↵
{↵
int n;↵
cin>>n;↵
if(n==3)↵
{↵
cout<<1<<endl;↵
cout<<3<<endl;↵
}↵
else if(n==5)↵
{↵
cout<<1<<endl;↵
cout<<5<<endl;↵
}↵
else if(n==7)↵
{↵
cout<<1<<endl;↵
cout<<7<<endl;↵
}↵
else if(n==9)↵
{↵
cout<<3<<endl;↵
cout<<3<<" "<<3<<" "<<3<<endl;↵
}↵
else↵
{↵
cout<<3<<endl;↵
cout<<3<<" ";↵
for(int i=3;2*i+3<=n;i+=2)↵
{↵
if(isPrime(i)&&isPrime(n-3-i))↵
{↵
cout<<i<<" "<<n-3-i<<endl;↵
break;↵
}↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
↵
The code seems to run with an worst case complexity of O(sqrt(n)*n) and in the given question n<=10^9 and still the submissions gets an AC in just **31ms**.↵
↵
Here you go with the solution.↵
[My Submission](https://mirror.codeforces.com/contest/584/submission/92408590)↵
↵
How is it possible? If I am wrong at finding out the complexity please help and tell how this works?
