Goldbach's conjecture

Hey guys:

One of the assignment for class is Goldbach's conjecture. Below is my code, but I am having problems with the actually computation. It goes into an infinite loop when it prints the first conjecture which is 4 =2 +2. To me, it doesn't seem like my code would do that, but obviously it does.

Can someone help me out and figure out why it's going to an infinite loop?

Thanks

Code:

#include<stdio.h>
#include<stdbool.h>


bool is_prime(int );

void goldbach(int n, int m)
{
  int i, j, k;


  for(i=n; i<= m; i+2)
    {
      for(j=2; j<= m; j++)
        {
          if(is_prime(j))
            {
              for(k=2; k<= m; k++)
                {
                  if(is_prime(k))
                    {
                      if( i == (j + k))
                        printf("&#37;d = %d + %d\n", i, j, k);

                    }
                }
            }
        }
    }


}

bool is_prime(int j)
{
  int divisor;

  for(divisor = 2; divisor*divisor <= j; divisor++)
    {
      if(j % divisor == 0)
        return false;
    }

  return true;

}

int main(void)
{

  int i, j, n, m;

  printf("\nEnter the value of n: ");
  scanf("%d", &n);

  printf("Enter the value of m: ");
  scanf("%d", &m);


  /* ********** SETS BOUNDRIES CORRECTLY ********** */

  if(n < 4)
      n = 4;

  if((n % 2) != 0)
      n = n + 1;

  if((m % 2) != 0)
    m = m - 1;

  /* ********************************************* */


  goldbach( n, m);

  printf("\n");



  return(0);
}

Code:

for(i=n; i<= m; i+2)

should be of course:

Code:

for(i=n; i<= m; i+= 2)

Didn't look the rest. The i+2 means nothing, you should get a warning, if not enable all warnings. If still nothing slap the compiler's creator

yeah I just realized it!

and I did not get any warnings about the i+2...

ok so my code works fine, but now it's double printing out numbers like: 8 = 3+5 and 8 = 5+3.

I can't figure out how I would keep it so that the first expression computed (for example, 8=3+5 rather than 8=5+3) is printed?

Any suggestions?

Code:

void goldbach(int n, int m)
{
  int i, j, k;

  for(i=n; i<= m; i+2)
      for(j=2; j<= m; j++)
          if(is_prime(j))
              for(k=2; k<= m; k++)
                  if(is_prime(k))
                      if( i == (j + k))
                        printf("&#37;d = %d + %d\n", i, j, k);

I only did this for the sake of my own sanity. Don't worry about changing the original code.

Ok, yeah it is printing it twice because you have no protection against it printing once for when it finds j and once for when it finds k.

I don't know what the Goldbach conjecture is off the top of my head, but just by looking at your code I can tell you two things:

1) It would be more efficient to generate a list of primes before you started your 'i' loop. Your isprime() function is going to be busy doing a LOT of redundant calculations.

2) Your k-loop probably isn't necessary if what you are trying to do is print all the ways 'i' can be expressed as the sum of two prime numbers. Furthermore, adjusting the upper bound of your 'j' loop would solve your duplicated printing problem. Of course, I'm not just going to tell you how - half the fun is figuring it out for yourself!

Wow... 202 posts and already being snide, and tactless. Welcome aboard, arpsmack.

Thanks...? I certainly hope you aren't insinuating that post-count has any correlation to the poster's intelligence or experience....

Originally Posted by arpsmack

Thanks...? I certainly hope you aren't insinuating that post-count has any correlation to the poster's intelligence or experience....

I am only insinuating a post-count has a correlation with cynicism. Nothing more.

I am wondering now if you know what being a cynic means... If anything, I am assuming the poster has enough ingenuity that I don't need to spell out all the details for him.

If he would like to ask me for more information, I would gladly oblige.

Fair enough.

Giving a nudge rather than a whole solution is what we're all about here!
It's all about making sure everyone exercizes that organ between their ears.

One option is to modify your k loop so that rather than going from 2 to m, it only covers the range of numbers that are greater than the current value of the j loop. Or you could simply add an if-statement testing for k being greater than j.

Really, arpsmack has given good general advice about the problem though. As it is, if m is large this function will end up being very very slow.