Thread: isPrime

  1. #1
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694

    isPrime

    So, I felt that many times people need a function to tell if a number is prime or not. Especially students. I have seen some relevant code in the forum to.

    But, I saw that people of my level and even higher provided algorithms that were not so efficient in my mind. Probably they didn't try enough to improve their implementations.

    So, I decided to write my function isPrime. If someone sees some way of improvement, then I would very glad˛ if he or she let me know!!

    I have uploaded the function to my corner of the web.

    But, for those that do not really like the css of my corner, I post the code here as well

    Code:
    #include <stdio.h>
    #include <math.h>
    
    int isPrime(const int);
    
    int main(void)
    {
            int i;
            for (i = 1 ; i <= 15 ; ++i)
                printf("%d is %sprime\n", i, isPrime(i) ? "" : "NOT ");
            return 0;
    }
    
    int isPrime(const int number)
    {
        int i, r, prime = 1;
        if (number != 2 && number % 2 == 0)
            prime = 0;
        else
            for (i = 3, r = sqrt(number) ; i <= r && prime ; i += 2)
                if (number % i == 0)
                    prime = 0;
        return prime; 
    }
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  2. #2
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    Did you know that all functions beginning with "is" are reserved for future use of ctype header (see C99 Draft, section 7.26 -> 7.26.2 #1) So by calling your function "isPrime", you are making your function non-standard!

    1 is not a prime number - Prime number - Wikipedia, the free encyclopedia

    And if you are doing a large range of numbers, a sieve is a much faster option -> The reason is that dividing takes longer than addition Sieve of Eratosthenes - Wikipedia, the free encyclopedia
    Fact - Beethoven wrote his first symphony in C

  3. #3
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    If you solve this problem, you are given a short paper on prime number identification as a gift -
    Problem 7 - Project Euler

    [edit]
    Whoops - I meant http://projecteuler.net/problem=10
    But both correct answers will give you a different short paper on prime number identification as a gift
    Problem 10's paper is better!
    [/edit]

    Tell me how you go
    Last edited by Click_here; 01-23-2013 at 06:36 PM.
    Fact - Beethoven wrote his first symphony in C

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I didn't know "is" was a reserved prefix for function names! Ack!

    Sieve of Eratosthenes is *wonderfully fast* - you will be amazed at how much faster it is.

  5. #5
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    Quote Originally Posted by Adak View Post
    I didn't know "is" was a reserved prefix for function names! Ack!
    I learnt that through a book Salem recommended me "C Unleashed" - Note that it is an advanced book (not for beginners) full of very useful stuff - Highly recommend it.
    Fact - Beethoven wrote his first symphony in C

  6. #6
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    If passed -1 will the program crash or what?

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Click_here
    Did you know that all functions beginning with "is" are reserved for future use of ctype header (see C99 Draft, section 7.26 -> 7.26.2 #1) So by calling your function "isPrime", you are making your function non-standard!
    That is an interesting point that I was not aware of. However...
    Quote Originally Posted by C99 Clause 7.26.2
    Function names that begin with either is or to, and a lowercase letter may be added to the declarations in the <ctype.h> header.
    This means that "isPrime" is safe. Furthermore, although the language is not entirely clear to me, but I believe that such names are not reserved anyway. It seems more of a notice that certain such names may be declared in the future in <ctype.h>, hence they should be avoided for future compatibility, but do not make functions with such names non-standard.
    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

  8. #8
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    Quote Originally Posted by laserlight View Post
    That is an interesting point that I was not aware of. However...

    This means that "isPrime" is safe. Furthermore, although the language is not entirely clear to me, but I believe that such names are not reserved anyway. It seems more of a notice that certain such names may be declared in the future in <ctype.h>, hence they should be avoided for future compatibility, but do not make functions with such names non-standard.
    Here is a quote from the textbook referenced below:

    (R. Heathfield, et al. (2000), "C Unleashed", "Reserved Names", Sams Publishing, Indiana USA,)
    "First, any identifier beginning with a leading underscore and then followed either by an uppercase letter or another underscore is reserved for use by the implementation..."
    "It's all to do with extensibility. The ANSI committee recognizes that languages grow or die... Specifically, the committee wanted to make room for new functions in the standard library, while minimizing the possibility of breaking existing code. To that end, they reserve certain letter combinations that are particularly likely to form the start of new function names. For example, anything beginning with "str" is reserved because, although there are already plenty of standard library functions beginning with "str", there is certainly much more useful functionality that could be provided for string-handling. To allow for this, the letter combination "str" is reserved. The same applies to "is" and "to" (to allow <ctype.h> to be extended), "mem" (for extra memory manipulation functions), "SIG" (for new signals_ and a number of other prefixes."

    I think that this argument is extremely likely to be the correct interpretation of the standard.
    Last edited by Click_here; 01-23-2013 at 11:40 PM.
    Fact - Beethoven wrote his first symphony in C

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > for (i = 3, r = sqrt(number) ; i <= r && prime ; i += 2)
    Watch this
    https://en.wikipedia.org/wiki/File:S..._animation.gif

    What you should have for i+=2 is something which uses the next known prime.

    For example, having checked 3, there is no point checking all further multiples of 3, such as 9, 15 etc.
    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.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by std10093 View Post
    I saw that people of my level and even higher provided algorithms that were not so efficient in my mind. Probably they didn't try enough to improve their implementations.
    Unfortunately you've committed what I've generally seen to be the worst performance blunder that people tend to make when writing primality tests...
    You've put the immensely expensive sqrt call, inside the loop. I'm guessing that you were not aware that a sqrt call is even more expensive that the modulus operation.

    You've also got a multiple part expression in your for loop condition (which I personally despise) where the only time that the second half is false is when you could just dorectly break out of the loop and avoid the needless test every time through the loop.

    And of course 1 is not prime.

    The part that you've done well on is the i += 2; which beats i++; but even taking the sqrt out of the loop and just using i++; would probably have been faster.
    Last edited by iMalc; 01-24-2013 at 12:25 AM.
    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"

  11. #11
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Quote Originally Posted by iMalc View Post
    Unfortunately you've committed what I've generally seen to be the worst performance blunder that people tend to make when writing primality tests...
    You've put the immensely expensive sqrt call, inside the loop. I'm guessing that you were not aware that a sqrt call is even more expensive that the modulus operation.
    But it is in the initial assignment part (evaluated once), and not the condition or step parts (which are evaluated every time).
    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. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Click_here
    I think that this argument is extremely likely to be the correct interpretation of the standard.
    I have my doubts: the whole 7.26 subclause is about future library directions. Thus, there is no mandate concerning current programs, but rather recommendations on what is likely to happen. Case in point: Heathfield correctly notes that "any identifier beginning with a leading underscore and then followed either by an uppercase letter or another underscore is reserved for use by the implementation", and indeed this is explicitly stated in clause 7.1.3, entitled "Reserved identifiers".

    Furthermore, Heathfield is technically incorrect concerning "is" and "to" because of the failure to mention "and a lowercase letter". Hence, isPrime and is_prime are definitely fine.
    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

  13. #13
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    WOW! I didn't expect so much feedback! And the feedback comes from some of the top users here.. Thank you very much!
    Also, thanks to this forum, I got this message from the TA of the C class : "Anyway (inofficially) you are ranked first in the class (and also the final exam). Maybe we shift around a bit with the points, as so far some students failed, but should not make much difference for you. "
    Thank˛ you - Ευχαριστώ˛ - Danke˛ - Grazie˛ (these are the languages I know, so don't get "offended", if I didn't say thanks in your language )

    About the code now..
    • 1 is not prime. Tim S. very good observation about the negative numbers too. Will fix it.
      From wiki :
      Code:
      Most early Greeks did not even consider 1 to be a number
      Didn't know that!
    • I didn't know about the prefix 'is'. But, if I succeed in implemented what Eratosthenes thought, then I will change the name.
    • Sieve of Eratosthenes. No comments needed. I don't know however if I had forgotten about it, or even didn't know about it. Probably the highest target now.
    • sqrt. It is a bit paradox. I remember a thread about primes I think, that I stated how slow is sqrt, taking into consideration the kernel time. Then iMalc came and said, that's not important, because the user won't notice the latency. Which, I think he is right. As Salem noticed, I have it in the initialized part of the for loop, so I am going to keep the sqrt.


    So, I did the modifications stated. They are simple, so I won't post it, but I uploaded here (hopefully I didn't miss something). Now let's try the idea of Eratosthenes (Ερατοσθένης). Then, I will take a look at the paper Click_here talked about.

    Also, I think a quote for Eratosthenes fits here :
    Code:
    Eratosthenes of Cyrene was a Greek mathematician, geographer, poet, athlete, 
    astronomer, and music theorist. He was the first person to use 
    the word "geography" in Greek and he invented the discipline of geography 
    as we understand it.
    Thanks again everybody for their answers.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  14. #14
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    It's ready! You can find it here.

    But now, I admit, I want to compare time of Eratosthenes's idea and the isPrime implementation.

    I think that it would be proper to test in Linux. Is this code ok to measure time?
    Code:
    #include <time.h>
    
     clock_t start, end;
     double cpu_time_used;
    
     start = clock();
     ... /* Do the work. */
     end = clock();
     cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    If not, can you suggest another way to measure it?
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  15. #15
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Hmm.. I have as N = 1.000.000, but I get as answer 0.0000 .. Maybe I am doing something wrong, don't I?

    //perform the same to isPrime and still output is zero.
    Last edited by std10093; 01-24-2013 at 09:34 AM.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

Popular pages Recent additions subscribe to a feed