Thread: Sos!!

    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2013
    Posts
    3
    Rep Power
    0

    Exclamation Sos!!


    i need help on this C programming problem.. it's finding a way that expresses an integer into a sum of four prime numbers

    the program should have an input similar to this:
    Sample Input
    3
    24
    36
    46

    and an output:
    Sample Output
    24: 3 11 3 7
    36: 3 7 13 13
    46: 11 11 17 7

    can anyone teach me how to do this? or make a program on this for me to study? thank you :)
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,407
    Rep Power
    1871
    http://en.wikipedia.org/wiki/Goldbach%27s_conjecture
    Since it's an even number, you can divide it by 2.
    This either gives you an equal pair of even numbers or an odd number.
    If it's odd, then +1 and -1 will give you a pair of even numbers.

    Then it's just a matter of working out a GC answer for the pair of even numbers you have.

    I suppose the first task would be to write some code that either verifies if a number is prime, or gives you a list of primes.
    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
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2013
    Posts
    3
    Rep Power
    0
    thank you for the help..:) do i have to use recursion on this problem?
  6. #4
  7. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,407
    Rep Power
    1871
    Does your assignment specifically mention that you have to use recursion?

    If not, then no, you don't have to use recursion.
    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
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2013
    Posts
    3
    Rep Power
    0
    what do i have to use then? can you teach me?
  10. #6
  11. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,407
    Rep Power
    1871
    > what do i have to use then? can you teach me?
    It would seem to be a waste of effort on my part.

    It's been two days since you posted, but so far you haven't shown a lot of effort.

    I mean, just reading the input data and printing things like
    "There are 3 numbers to process"

    and
    Processing 24
    Processing 36
    Processing 46

    would go some way to assuring us that you're taking this assignment seriously, and not just looking for a free answer on a plate.

    Another useful step would be to write a function called isPrime(int n) which returns true if n is prime.

    You see, before we get anywhere near the 'sum of two primes' part of the problem, there is a lot of initial code you can be getting on with.

    And there's no point explaining the details of GC if you can't even read the first input number properly.
    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
  12. #7
  13. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2013
    Location
    Pennsylvania, USA
    Posts
    35
    Rep Power
    2
    One way would be to know all the prime numbers below the input number. Then, use some logic to always use the first two or three smallest numbers plus the prime number that adds to the desired input number.

    The first few primes are:

    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,

    Examples to get 21:

    2 + 3 + 5 = 10

    Then:

    21 - 10 = 11

    Check if 11 is a prime. It is; so, we're done. Otherwise, we would use a different set of smaller numbers. I would give you more code, but I've been called out on this forum before for helping too much.
    Last edited by dynamicflash; October 14th, 2013 at 04:49 PM.
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2013
    Location
    China
    Posts
    6
    Rep Power
    0

    A nasty solution


    #include <stdio.h>
    int isprime(int);
    int main (void)
    {
    int bum = 24;
    int a1 = 2, a2 = 2, a3 = 2, a4 = 2;

    for (a1 = 2; a1 <= bum -1 - a2 - a3 - a4; a1++ )
    {
    if (isprime(a1) == 0)
    continue;
    else
    a1 = isprime(a1);
    }

    while ( a1 != isprime(a1))
    {
    a1--;
    }

    for (a2 = 2; a2 <= bum - 1-a1-a3-a4; a2++ )

    {
    if (isprime(a2) == 0)
    continue;
    else
    a2 = isprime(a2);
    }

    while ( a2 != isprime(a2))
    {
    a2--;
    }

    for (a3 = 2; a2 <= bum -1 -a1-a2-a4; a3++ )

    {
    if (isprime(a3) == 0)
    continue;
    else
    a3 = isprime(a3);
    }

    while ( a3 != isprime(a3))
    {
    a3--;
    }

    for (a4 = 2; a4 <= bum - 1 -a1-a2-a3; a4++ )

    {
    if (isprime(a4) == 0)
    continue;
    else
    a4 = isprime(a4);
    }

    while ( a4 != isprime(a4))
    {
    a4--;
    }

    printf("%5d %5d %5d %5d", a1, a2, a3, a4);

    return 0;
    }


    int isprime(int num)
    {
    int i;
    int k = 1;
    for (i = 2; i*i <= num; i++)
    {
    if ((num%i) != 0)
    {
    k = 1;
    continue;
    }
    else
    {
    k=0;
    break;
    }
    }

    if (k == 0)
    return 0;
    if (k == 1)
    return num;


    }
  16. #9
  17. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2013
    Location
    China
    Posts
    6
    Rep Power
    0
    Originally Posted by Mich Song
    #include <stdio.h>
    int isprime(int);
    int main (void)
    {
    int bum = 24;
    int a1 = 2, a2 = 2, a3 = 2, a4 = 2;

    for (a1 = 2; a1 <= bum -1 - a2 - a3 - a4; a1++ )
    {
    if (isprime(a1) == 0)
    continue;
    else
    a1 = isprime(a1);
    }

    while ( a1 != isprime(a1))
    {
    a1--;
    }

    for (a2 = 2; a2 <= bum - 1-a1-a3-a4; a2++ )

    {
    if (isprime(a2) == 0)
    continue;
    else
    a2 = isprime(a2);
    }

    while ( a2 != isprime(a2))
    {
    a2--;
    }

    for (a3 = 2; a2 <= bum -1 -a1-a2-a4; a3++ )

    {
    if (isprime(a3) == 0)
    continue;
    else
    a3 = isprime(a3);
    }

    while ( a3 != isprime(a3))
    {
    a3--;
    }

    for (a4 = 2; a4 <= bum - 1 -a1-a2-a3; a4++ )

    {
    if (isprime(a4) == 0)
    continue;
    else
    a4 = isprime(a4);
    }

    while ( a4 != isprime(a4))
    {
    a4--;
    }

    printf("%5d %5d %5d %5d", a1, a2, a3, a4);

    return 0;
    }


    int isprime(int num)
    {
    int i;
    int k = 1;
    for (i = 2; i*i <= num; i++)
    {
    if ((num%i) != 0)
    {
    k = 1;
    continue;
    }
    else
    {
    k=0;
    break;
    }
    }

    if (k == 0)
    return 0;
    if (k == 1)
    return num;


    }
    Hey everyone, i'm new here and new to the C programming (started to learn c from August). I know the code is very stupid but that's all i got. I worked it out all by myself (even the isprime() function) in the past 2 days starting from the day i registered in.
    Can anyone help me for the below two things
    1. I'm still wondering why I have to minus 1 in front of each variable-bum to make the program run correctly.
    2. can anyone improve the code to make it more compact?

    Thanks a lot!
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2013
    Location
    China
    Posts
    6
    Rep Power
    0

    About the scanf


    I edit these codes online on codepad.org, so I cannot use scanf function. The user have to change the number of variable-bum everytime he runs.

    I just finished 12 chapters-articles and excercises of C primer pluse, so I don't have much profound knowledge concerning to c programming.

    So if anyone would help me the above 2 questions, can you only apply the simple knowledge confining to loop, iteration, recursion, or anything contains in the first 12 chapters if you read that book too :) ?

IMN logo majestic logo threadwatch logo seochat tools logo