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.

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.)

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.

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.)

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.

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.

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.

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").

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.

Quote:

---

Originally Posted by a23190

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?

I would probably use Fermat's little theorem if I was doing it with a calculator.

Quote:

---

Originally Posted by a23190

I would probably use Fermat's little theorem if I was doing it with a calculator.

---

Now I know you're trolling.

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.

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?)

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.

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;
    }
}

---