Блог пользователя obliviousz

Автор obliviousz, история, 4 года назад, По-английски

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?

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Link to the problem is not working.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

That might be the complexity if there was no break statement. But because of the break, the loop terminates. The correct question to ask would be, is there a way to prove that the loop will terminate quickly, i.e. we will quickly find those 2 primes without checking all possibilities.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by obliviousz (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by obliviousz (previous revision, new revision, compare).

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Proving that this does not give TLE is probably equivalent to proving Goldbach's conjecture itself.

However of we pretend that the prime numbers are simply a random subset of the naturals with approximately $$$n / \log n$$$ primes below $$$n$$$, then you can calculate the probability that we find a match in the first [whatever small number] of tries. It should be quite high.