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; I just started using C++ no more than a week ago. I have to write a program that solves Goldbach's ...

  1. #1
    Registered User
    Join Date
    Jul 2011
    Posts
    7

    Goldbach's Conjecture problem

    I just started using C++ no more than a week ago. I have to write a program that solves Goldbach's conjecture (Wikipedia provides a simple overview if you don't know what this is), but since my program will be dealing mostly will smaller values, speed and efficiency aren't of the highest importance. I have found codes that are already written online, but I need to come up with one of my own. So far, this is what I have written:


    Code:
    #include <iostream> 
    using namespace std; 
     
    int main () {
     
        long int x; 
        int a,b;
     
        cout << "Enter the number: ";
        cin >> x; 
        cout << endl; 
     
        if (x<=2) {
     
        cerr << "Goldbach's conjecture only works for even integers greater than 2. ";
        cout << endl;
        cout << endl;
     
        return 0; 
    } 
     
        if ((x%2)!=0) {
        cerr << "Goldbach's conjecture only works for even integers. ";
        cout << endl; 
        cout << endl;
     
        return 0;
    }
     
         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;
     
            }
    }
    }
    return 0; 
    }
    This program takes the value that is entered and splits it into as many pairs as possible that add up to the original input. Is there a way for me to limit this so that only the pairs containing two primes appear? Or if this is not possible, what else should I do? Remember, this doesn't have to very fast or that efficient.

    Thanks for reading.
    Last edited by Salem; 08-01-2011 at 02:03 AM. Reason: restored original post for context

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You need to test whether a and b are prime.

    (And there's a lot fewer "pairs of numbers that add up to x" then there are "pairs of prime numbers", so you should start with the numbers that add to x.)

  3. #3
    Registered User
    Join Date
    Jul 2011
    Posts
    7
    I know I need to test whether a and b are prime, but I cannot figure out how to do it correctly thus far. (That is why I posted.) Also, I was referring only to the pairs of primes that add up to x, not all pairs of prime numbers.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Do you know what "prime" means? (EDIT: And if you had a way to find "the pairs of primes that add up to x", then you'd be done, because that's what you're looking for.)
    Last edited by tabstop; 07-31-2011 at 11:33 PM.

  5. #5
    Registered User
    Join Date
    Jul 2011
    Posts
    7
    Perhaps you don't understand what I am asking or you are confused on the definition of a prime number. A prime number only has a two divisors, one and itself. The program I wrote above finds all numbers that add up to the input (including all cases where both a and b are prime). I am trying to just output those specific prime combinations and none of the rest. Since, like I said, I've only been using C++ for about a week, I don't know the code to use to make this happen.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Right. You've got pairs. Now check whether the numbers are prime. You've got the definition down -- so do it, already. Given a number, determine what factors it has and, specifically, whether it has divisors other than itself and 1.

  7. #7
    Registered User
    Join Date
    Jul 2011
    Posts
    7
    That is what I want the program to do, check whether a and b are prime, and then output only the prime factors that add up to x and none of the rest. I do NOT know how to do this, which is why I posted for help.

    You seem to be repeatedly misunderstanding me. Goldbach's conjecture states that ANY even integer greater than 2 can be expressed as the sum of two primes. It can be expressed as the sum of two non-primes as well, but that isn't what we are talking about. For example, if I put 8 into the program above, it would output:

    2 and 6
    3 and 5
    4 and 4

    I only want it to output:

    3 and 5.

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I think you misunderstand what this board is. This board is not you handing us a problem and us handing you code. This board is for advice and the always-popular "second set of eyes" to spot things that are wrong. If you deliberately avoid writing a part of your program, we are deliberately going to also not write that part of your program. Read the homework policy, which is a sticky on the front page of the forum, and try again (and by try again I mean "try writing a check for whether a number is a prime").
    Salem likes this.

  9. #9
    Registered User
    Join Date
    Jul 2011
    Posts
    7
    This isn't homework. I am just a high school student who is writing this for fun. Secondly, I wasn't asking anyone to write the program for me. I was asking for someone to steer in the right direction with perhaps some information (from an outside source or from an educated user) on how I can someway limit this. Also, I don't know if this program as is can even be minutely altered to check for primes. I've been trying for the past few hours myself and haven't had any luck. Thank you for not helping in the slightest and asking if I know what a prime number is. You have been completely worthless.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by a23190 View Post
    I was asking for someone to steer in the right direction with perhaps some information (from an outside source or from an educated user) on how I can someway limit this.
    If that's what you wanted, then why didn't you use it when it was provided to you? I'll say it again: You need to check whether each number has a divisor (other than itself and 1). This is not complicated, or difficult, or in any way out of your abilities. But you actually have to sit down and do it. If you had a calculator and I gave you the number 2238567, how would you tell whether it was prime?

  11. #11
    Registered User
    Join Date
    Jul 2011
    Posts
    7
    I would probably use Fermat's little theorem if I was doing it with a calculator.

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by a23190 View Post
    I would probably use Fermat's little theorem if I was doing it with a calculator.
    Now I know you're trolling.

  13. #13
    Registered User
    Join Date
    Jul 2011
    Posts
    7
    How is that trolling? It is faster, although sometimes deceptive, than dividing it by up to the square root of n. The Miller-Rabin test would also work if I was forced to do it by hand.

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You're assuming you have buttons other than +, -, *, and /. Go with "dividing it up to the square root of n". The "sometimes deceptive" part is also a problem (why accept "right most of the time" when you can get "right all of the time" for less work -- remember what the computer does will take zero time for the numbers you can actually type in on the keyboard?)

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    Sometimes people get off on the wrong foot, as both of you have.

    The problem so far is that you have already approached the problem the wrong way. You don't need nested loops for a and b. For each 'a', there is only one possible value for 'b' and it's equal to x-a. So remove the nest loop and see where that gets you.

    Also make sure you indent the code properly. Coding is not a bracket counting exercise.
    Post updated code for what you have after that.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Page 1 of 2 12 LastLast
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, 07:01 PM
  2. Goldbach's Conjecture
    By cashmerelc in forum C Programming
    Replies: 7
    Last Post: 07-19-2010, 10:41 PM
  3. Goldbach's conjecture
    By dcwang3 in forum C Programming
    Replies: 10
    Last Post: 10-14-2008, 01:34 AM
  4. Replies: 3
    Last Post: 11-13-2005, 01:53 AM
  5. Goldbach Conjecture
    By StarOrbs in forum C++ Programming
    Replies: 19
    Last Post: 03-17-2005, 03:42 PM

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