# Thread: isPrime

1. ## 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;
}```

2. 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

3. If you solve this problem, you are given a short paper on prime number identification as a gift -
Problem 7 - Project Euler

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

4. 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. Originally Posted by Adak
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.

6. If passed -1 will the program crash or what?

Tim S.

7. 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...
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.

8. Originally Posted by laserlight
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.

9. > 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.

10. Originally Posted by std10093
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.

11. Originally Posted by iMalc
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).

12. 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.

13. 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.

14. 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?

15. 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.

Popular pages Recent additions