Thread: Goldbach's Conjecture

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    26

    Goldbach's Conjecture

    I have been tasked with writing a program that allows a user to input a lower bound and an upper bound so the program can show that every even number between the two is the sum of two primes.

    I.E.

    4 = 2 + 2
    6 = 3 + 3


    I have written a program that determines whether a number is prime but I'm not really sure how to get the two primes that add up to a given number. Any ideas?

    In other words, I know how to show the even numbers, I just don't know how to approach displaying the two primes.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    For each pair of positive integers which add up to the given number, you have to check whether both are prime. For any even number >= 6, both numbers have to be odd to be prime, since 2 is the only even prime, and the two numbers must either be both even, or both odd, to add up to an even number. Therefore you can simplify the program by assuming that the lower bound is >= 6, and only consider odd pairs. Furthermore, you can without loss of generality assume that the first number is less than or equal to the second (after all, one of the two numbers is less than or equal than the other, and addition is commutative). So, for example, for 20 you have to check

    3 + 17
    5 + 15
    7 + 13
    9 + 11

    You use a loop to run through each of the 4 possibilities. In this case, it discovers that the very first pair are both prime, so it can print them and exit.

  3. #3
    Registered User
    Join Date
    Sep 2007
    Posts
    26
    Okay, I have the program more or less written but the output shows nothing but zeros for the two prime numbers being added.

    i.e.

    4 = 0 + 0
    6 = 0 + 0
    etc..

    Here is my code:
    Code:
    // This program demonstrates Goldbach's Conjecture
    // that every even number greater than 2 is the sum
    // of two prime numbers.  The user is asked to input
    // an upper and lower bound and the program shows each even number
    // and shows two prime numbers that sum up to the even number.
    
    #include <stdio.h>
    
     int i, num, n, m, a, b, k, x, j, number;
    
            int goldbach(i, a, b)
            {
                    // Since the highest number we need to check for prime is half the total value
                    // we only need to check up to that number
    
                    for (x = 2; x <= (i / 2); ++x)
                    {
                            if(prime(x) && prime(i - x))
                            {
                                    a = x;
                                    b = i - x;
                                    return 1;
                                    break;
                            }
    
    
                    }
            }
    
    
    int prime(j)
    {
            int result = 1, k;
    
            if(j == 1 || j == 2)
            {
                    result = 0;
            }
            else
            {
                    for(k=2;k<=j/2;k++)
                    {
                            if(j%k == 0)
                            {
                                    result = 1;
                                    break;
                            }
                    }
            }
    
            if(result == 0)
                    return 1;
            else
                    return 0;
    }
    
    
    main (void)
    {
    
    
            printf("Please enter the value of n: ");
            scanf("%d", &n);
            printf("Please enter the value of m: ");
            scanf("%d", &m);
    
            if (n < 4)
            {
                    num = 4;
            }
            else
            {
                    if (n%2 != 0)
                    {
                            num = n + 1;
                    }
            }
    
            for (i = num; i <= m; i += 2)
            {
                    if(goldbach(i, a, b))
                    {
                            printf("%d = %d + %d \n", i, a, b);
                    }
                    else
                    {
                            printf("Goldbach's Conjecture fails for this number: %d \n", i);
                    }
            }
    }
    Any ideas?

    I'm probably just overlooking something obvious, but damned if my eyes aren't beginning to rebel.

    Thanks in advance for taking the time to look it over

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Well, for starters your function goldbach(i, a, b) doesn't actually do anything with the variables a and b. It assigns TO them internally, but they don't affect anything else. The function should take a single argument i. It also fails to return 0 in case it doesn't find a pair of primes adding to i. The reason it's printing "0 + 0" is that a and b are global variables which are initialized to zero by default (BTW, you really shouldn't be using globals) and the function goldbach(i, a, b) isn't modifying the values of a and b, since you pass them by value, so the function only modifies its local copies of a and b.

    Edit: Actually, since you want the goldbach function to return the two primes adding up to i, you should either:

    1) Pass pointers to a and b, so that the function can write to them, or

    2) Just use the return value. Return the lesser of the two primes that add up to i, or 0 if no such pair exists. So you could declare it as
    Code:
    int goldbach(int i);
    and then goldbach(8) == 3 (since the first pair of primes adding up to 8 is 8 == 3 + 5).

    Edit: A few other minor points:

    1) main() should explicitly return int:
    Code:
    int main(void) {
    2) You should have an explicit "return 0;" at the end of main(), since in C90, without this, the return value is undefined.

    3) In prime(), you don't need the variable "result". Just use early returns instead. You're allowed to have multiple return statements anywhere in a function you want, not just at the end.

    4) The declaration of prime(j) should be
    Code:
    int prime(int j) {
    Last edited by robatino; 10-19-2007 at 06:14 PM.

  5. #5
    Registered User
    Join Date
    Jul 2010
    Posts
    1
    hey cashmerelc, the program you gave, if it runs, would take loads of time to do so. I have made this program where user inputs an even number and the computer prints all possible combinations of prime numbers which add up to give that number. Check it out:

    Code:
    #include<stdio.h>
    #include<math.h>
    int primecheck(long int x);
    main()
    {
      long int a,b,c;
      int i,j,k;
      label: printf("Enter the number: ");
      scanf("%ld",&a);
      if ((a%2)==1)
      {
      	printf("\nThat's an odd number you dumbo! Goldbach's Conjecture involves an even number!\n\n");
      	goto label;
      }
      for (b=2;b<a;++b)
      {
      	for (c=2;c<a;++c)
      	{
    	 j=primecheck(b),k=primecheck(c);
    	 if ((j==0) && (k==0) && (b+c==a) && (b<=c))
    	 printf("\n%4ld + %4ld = %4ld",b,c,a);	
      }
      }
      printf("\n\n");
    }
    int primecheck(long int x)
    {
    long int i=2;
    while (i<x)
    {
    if ((x%i)==0)
    break;
    ++i;
    }
    if (i==x)
    return(0);
    else
    return(1);
    }

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    3-year bump not really adding much...
    Closed.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    Not closed.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by User Name:
    Not closed.
    Good point. It is now.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Goldbach's conjecture
    By dcwang3 in forum C Programming
    Replies: 10
    Last Post: 10-14-2008, 01:34 AM
  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