Why doesnt it give TLE?

Правка en3, от obliviousz, 2020-09-10 11:40:19

I was solving D. Dima and Lisa 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. How is the break statement working and finding out the two primes? Is it because of weak testcase?

Here you go with the solution. My Submission

How is it possible? If I am wrong at finding out the complexity please help and tell how this works?

Теги #number theory, #math, #brute force

История

 
 
 
 
Правки
 
 
  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)