Why doesnt it give TLE?
Разница между en1 и en2, 7 символ(ов) изменены
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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский obliviousz 2020-09-10 11:40:19 99
en2 Английский obliviousz 2020-09-10 11:37:32 7 Tiny change: 'Lisa](http://https://co' -> 'Lisa](https://co'
en1 Английский obliviousz 2020-09-10 11:22:03 1771 Initial revision (published)