Like Tree1Likes

Goldbach's Conjecture problem

This is a discussion on Goldbach's Conjecture problem within the C++ Programming forums, part of the General Programming Boards category; Some optimizations step by step: Code: for (a=2; a<=x; a++) { for (b=2; b<=x; b++) { if ( (x>2) && ...

  1. #16
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    682
    Some optimizations step by step:

    Code:
    for (a=2; a<=x; a++)
    {
        for (b=2; b<=x; b++)
        {
            if ((x>2) && ((x%2)==0) && (a<=b) && (a+b==x))
            {
                cout << a << " and " << b << endl; 
            }
        }
    }
    The red condition is unnecessary, since the input has already been verified. When it comes to the orange test, it can be moved to the inner loop's condition:

    Code:
    for (b=2; b<=x; b++)
    {
        for (a=2; a<=b; a++)
        {
            if (a+b==x)
            {
                cout << a << " and " << b << endl; 
            }
        }
    }
    Note that I reordered the loops, now the 'b' is outer.
    Going this way you can do what iMalc said eliminating the last condition.
    Given 'a' in set: <2..b> there can be only one (or zero) 'a', such that (a + b = x), and this is (a = x - b):

    Code:
    for (b=2; b<=x; b++)
    {
        cout << x - b << " and " << b << endl; 
    }
    If (b == x) then (a == 0), if (b == x - 1) then (a == 1). Both 0 and 1 are not primes:

    Code:
    for (b=2; b < x - 1; b++)
    {
        cout << x - b << " and " << b << endl; 
    }
    The code is much cleaner now, I think you will manage to implement IsPrime function. Just in case you get stuck:

    Code:
    for (b=2; b < x - 1; b++)
    {
        if (IsPrime(b) && IsPrime(x - b))
        {
            cout << x - b << " and " << b << endl;
        }
    }
    Last edited by kmdv; 08-01-2011 at 04:44 AM.
    I never put signature, but I decided to make an exception.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Collatz's Conjecture
    By KAUFMANN in forum C Programming
    Replies: 15
    Last Post: 06-29-2011, 08:01 PM
  2. Goldbach's Conjecture
    By cashmerelc in forum C Programming
    Replies: 7
    Last Post: 07-19-2010, 11:41 PM
  3. Goldbach's conjecture
    By dcwang3 in forum C Programming
    Replies: 10
    Last Post: 10-14-2008, 02:34 AM
  4. Replies: 3
    Last Post: 11-13-2005, 02:53 AM
  5. Goldbach Conjecture
    By StarOrbs in forum C++ Programming
    Replies: 19
    Last Post: 03-17-2005, 04:42 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21