/!\help In C Please /!\

Discussion in 'Programmer's Corner' started by !!Miss.EE!!, Apr 2, 2008.

  1. !!Miss.EE!!

    Thread Starter Active Member

    Oct 17, 2007
    38
    0
    Hi

    How are u all ^__^

    I have an assignment that asks to write a function that determines if a number is prime and following questions ....

    but untill know the programm doesn't want to work !!!:mad:

    my question is that ...

    the prime funtion is divisible only by one and itself ... thus the reminder must equal either the number it self or 0 ...

    OK trying to write this in C whiten my hair ... :eek:

    so please any one can explain more for me :p



    Regards
     
  2. hgmjr

    Moderator

    Jan 28, 2005
    9,030
    214
    Can you provide a flowchart of your prime number algorithm? Then maybe we can give you some suggestions on how it might be improved.

    hgmjr
     
  3. Colin Mac

    Member

    Mar 11, 2008
    18
    0
    Look up the modulus operator. Your answer lies there.
     
  4. Mark44

    Well-Known Member

    Nov 26, 2007
    626
    1
    A prime number is one that is divisible only by one and itself.

    When you check a number to see whether it's prime, you need to divide the number by all primes up to the integer closest to and less than the square root of the number. For example, to check 39, you would need to divide by 2, then 3, and then 5. (The square root of 39 is 6 plus a little bit, but 6 isn't prime, so you can stop at 5.) You need a loop to do these divisions, one iteration per division.
    Mark
     
  5. ¥öK'žy

    Member

    Mar 27, 2008
    19
    0
    Use modulus fuction to divide your number one by one.
    ex:
    int mod,flag=0; //mod is the input number;
    scanf("%i",mod);
    for (int i=1;i<=mod;i++)
    {
    if(mod%i==0)
    {
    flag++;
    }
    }
    if(flag==2) //prime number ONLY divisible by one and itself
    {
    printf("%i is a prime",mod);
    }

    That's it. it's that simple... ^^
     
  6. Mark44

    Well-Known Member

    Nov 26, 2007
    626
    1
    Any arguments in scanf appearing after the format string have to be addresses.
    What you need is
    Code ( (Unknown Language)):
    1.  
    2. scanf("%i", &mod);
    3.  
    Aside from that, there is no need to loop through every integer from 1 to mod. At the minimum you can omit every even integer larger than 2, since it is guaranteed not to be prime.
    Mark
     
  7. ¥öK'žy

    Member

    Mar 27, 2008
    19
    0
    Yup, my bad, its a typo... Since I type it manually...

    What about 9??? If you just use every even integer then 9 would be a prime too right??
     
  8. Mark44

    Well-Known Member

    Nov 26, 2007
    626
    1
    No, I'm NOT saying that after you eliminate the even integers larger than 2 you'll be left only with primes. There are lots of odd nonprimes: 9 (as you pointed out), 15, 21, 27, ...
    But if you eliminate the even integers right off the bat, you essentially double the speed of your routine.
     
  9. sixstringartist

    Member

    Apr 8, 2008
    18
    0
    People approach programming in different ways but it is generally a good idea to solve the program on paper (flowchart) before starting to code.

    As Mark44 has explained, you can do a special case check for divisible by 2 and then omit other even numbers. Another optimization would be to omit any number above 1/2 of the number you are evaluating.
     
  10. ¥öK'žy

    Member

    Mar 27, 2008
    19
    0
    Oh I see.. I'm confused when you say "there is no need to loop"....
     
  11. Mark44

    Well-Known Member

    Nov 26, 2007
    626
    1
    ¥öK'žy,
    I'm not sure whether you're still confused, or if my explanation cleared it up. In case you still are confused, the code you showed earlier in this thread has a for loop that runs through all the integers from 1 to mod, the number you're checking whether it's a prime. Going back to the example I gave earlier, if you're checking 39, it's very inefficient to check every integer from 1 to 39. It's sufficient to divide only by 2, 3, and 5. You don't need to go all the way to half of 39 (or 19) , as sixstringartist said--you can quit at the greatest odd integer less than sqrt(39), or 5. I hope that's clear.
     
  12. Kelth

    Member

    Mar 4, 2008
    12
    0
    Couldn't one just divide the number by say 2 through 9 and if it is divisible then it is not prime; and if not, then it is prime? Since I believe that any non-prime natural number is dividable by a natural number between 2 and 9.
     
  13. Mark44

    Well-Known Member

    Nov 26, 2007
    626
    1
    Sorry, but that won't work. A counterexample to your statement is 143. It's not divisible by 2, 3, 5, 7, or 9, but it's not prime.

    If every nonprime were divisible by an integer between 2 and 9, then public key encryption absolutely woudn't work. The basis of this encryption algorithm is a very large composite number (i.e., nonprime) made up of two large prime factors. The numbers involved are so large that it takes even the current generation of computers an inordinate amount of time to break them into their prime factors.
    Mark
     
  14. ¥öK'žy

    Member

    Mar 27, 2008
    19
    0
    Yeah that's clear me enough.
    Just never thought if we can quit at the greatest odd integer less than the sqrt of the integer.
    Thanx.
     
  15. Mark44

    Well-Known Member

    Nov 26, 2007
    626
    1
    Here's how that works.

    Suppose you have a number n that is not prime. There are two possibilities: it's a perfect square (like 36 or 81), or it's not.

    Case 1. n is a perfect square
    Two of the factors, clearly are \sqrt{n} and \sqrt{n}, and both of these are integers.

    Case 2. n is not a perfect square
    Since n is not a perfect square, \sqrt{n} is not an integer. Because we're assuming that n is not a prime, it must have integer factors a and b, where a*b = n. Necessarily one of these factors, call it a, is smaller than \sqrt{n}. The other factor, call it b, has to be larger than \sqrt{n}.

    Here's an example. Let n = 65. Since the \sqrt{65} is a little larger than 8, we don't need to check any numbers larger than 8. In fact, we only need to check up to 7.

    If I divide by 2, I get a remainder.
    If I divide by 3, I get a remainder.
    Skip 4.
    If I divide by 5, there's no remainder, which says that 5 is a factor.
    Skip 6.
    If I divide by 7, I get a remainder.

    I could go all the way up to 65/2, or 32 (rounding down), as someone suggested earlier, but any checks past 7 are a waste of time. The next number that divides evenly is 13, but I could have figured that out, since I already knew that 5 was a divisor (5 * 13 = 65).

    Notice that 5 < \sqrt{65} and 13 > \sqrt{65}, in agreement with what I said earlier.

    Mark
     
  16. ¥öK'žy

    Member

    Mar 27, 2008
    19
    0
    Thanx for the explanation. I've already try it with the calculator before read your reply T_T. And its true. thanx again.
     
Loading...