Thread: Goldbach's conjecture

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    116

    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);
    }
    Last edited by dcwang3; 10-13-2008 at 05:30 PM.

  2. #2
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    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

  3. #3
    Registered User
    Join Date
    Feb 2008
    Posts
    116
    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?

  4. #4
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    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.

  5. #5
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    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!
    Last edited by arpsmack; 10-13-2008 at 06:01 PM.

  6. #6
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Wow... 202 posts and already being snide, and tactless. Welcome aboard, arpsmack.

  7. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    Thanks...? I certainly hope you aren't insinuating that post-count has any correlation to the poster's intelligence or experience....

  8. #8
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Quote Originally Posted by arpsmack View Post
    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.

  9. #9
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    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.

  10. #10
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Fair enough.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Goldbach's Conjecture
    By cashmerelc in forum C Programming
    Replies: 7
    Last Post: 07-19-2010, 10:41 PM
  2. Godbach conjecture!!
    By Leojeen in forum C Programming
    Replies: 10
    Last Post: 04-20-2008, 06:42 PM
  3. Replies: 3
    Last Post: 11-13-2005, 02:53 AM
  4. Goldbach Conjecture
    By StarOrbs in forum C++ Programming
    Replies: 19
    Last Post: 03-17-2005, 04:42 PM