Bugs in an is_prime() implementation

[lovecreatesbea...]

Hello experts,

The following is_prime function doesn't call a library function and it
works.

Does it have bugs like "integer overflow": int factor; factor * factor,
or it's not single entry/exit, or others... Thank you.

/*return 0 if num is a prime number otherwise 1*/
bool is_prime(int num)
{
int factor;
if (num < 2) return 1;
for (factor = 2; factor * factor <= num; factor++)
if (num % factor == 0)
return 1;
return 0;
}

#include <stdio.h>
int main(void)
{
for (int i = 0; i < 1000; i++)
if (is_prime(i))
printf("%d", i) ;
return 0;
}

/*
Run: C:\MinGW\bin\mingw32-make.exe
gcc -ansi -pedantic -Wall -W -c -o a.o a.cpp
gcc a.o b.o -o a.out

Press the Enter key to return to Source Insight...

Run: D:\working\c\a.out
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 103 1
07 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197
199 211 2
23 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313
317 331 3
37 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439
443 449 4
57 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571
577 587 5
93 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691
701 709 7
19 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829
839 853 8
57 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977
983 991 9
97
Press the Enter key to return to Source Insight...
*/

 

[Guest]

[C++ code]

This group deals with C, not C++. Go ask this in comp.lang.c++.

 

[Ian Collins]

[C++ code]

This group deals with C, not C++. Go ask this in comp.lang.c++.

Excuse me, but with the addition of an include of <stdbool.h> the code
is legal C.

 

[Guest]

[C++ code]

This group deals with C, not C++. Go ask this in comp.lang.c++.

Excuse me, but with the addition of an include of <stdbool.h> the code
is legal C.

The code can be modified to become valid C99. The code as is is valid
C++ (with different behaviour than claimed by the OP) and compiled in
C++ mode.

 

[Ian Collins]

Hello experts,

The following is_prime function doesn't call a library function and it
works.

Does it have bugs like "integer overflow": int factor; factor * factor,
or it's not single entry/exit, or others... Thank you.

/*return 0 if num is a prime number otherwise 1*/
bool is_prime(int num)
{
int factor;
if (num < 2) return 1;
for (factor = 2; factor * factor <= num; factor++)
if (num % factor == 0)
return 1;
return 0;
}

Lots of mixed idioms, if you are using C99, use true and false, not 0 and 1.

You logic appears to be arse about face, returning 1 if the number has a
factor.

#include <stdio.h>
int main(void)
{
for (int i = 0; i < 1000; i++)
if (is_prime(i))
printf("%d", i) ;
return 0;
}

/*

Run: D:\working\c\a.out
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 103 1
07 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197
199 211 2
23 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313
317 331 3
37 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439
443 449 4
57 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571
577 587 5
93 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691
701 709 7
19 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829
839 853 8
57 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977
983 991 9
97
Press the Enter key to return to Source Insight...
*/

This can't be the output of the above, your printf doesn't include any
spaces and the logic is wrong.

 

[Richard Heathfield]

Ian Collins said:

[C++ code]

This group deals with C, not C++. Go ask this in comp.lang.c++.

Excuse me, but with the addition of an include of <stdbool.h> the code
is legal C.

True, although it's a legal C for which hardly anyone has a conforming
compiler. Nevertheless, the way he's compiling it indicates pretty clearly
that he thinks he's using C++. Why else would he name his source file
a.cpp?

 

[Ian Collins]

(e-mail address removed) wrote:


[C++ code]


This group deals with C, not C++. Go ask this in comp.lang.c++.

Excuse me, but with the addition of an include of <stdbool.h> the code
is legal C.

The code can be modified to become valid C99. The code as is is valid
C++ (with different behaviour than claimed by the OP) and compiled in
C++ mode.

Leaving out header files in posted snippets is a common mistake.

 

[Guest]

Harald van Dijk wrote:

(e-mail address removed) wrote:


[C++ code]


This group deals with C, not C++. Go ask this in comp.lang.c++.


Excuse me, but with the addition of an include of <stdbool.h> the code
is legal C.

The code can be modified to become valid C99. The code as is is valid
C++ (with different behaviour than claimed by the OP) and compiled in
C++ mode.

Leaving out header files in posted snippets is a common mistake.

He didn't leave out <stdio.h>, and adding <stdbool.h> would make it
invalid C++ (which, again, he's compiling his code as).

Another point: if he compiled it with the given compiler options as C
code, gcc would attempt to conform to C90, which does not allow
<stdbool.h> and declarations in for statements.

 

[Ian Collins]

He didn't leave out <stdio.h>, and adding <stdbool.h> would make it
invalid C++ (which, again, he's compiling his code as).

Another point: if he compiled it with the given compiler options as C
code, gcc would attempt to conform to C90, which does not allow
<stdbool.h> and declarations in for statements.

OK, OK. I didn't spot the compile line, I just read the (what appeared
to be C99) code.

 

[Kelly]

Hello experts,

The following is_prime function doesn't call a library function and it
works.

Does it have bugs like "integer overflow": int factor; factor * factor,
or it's not single entry/exit, or others... Thank you.

/*return 0 if num is a prime number otherwise 1*/
bool is_prime(int num)
{
int factor;
if (num < 2) return 1;
for (factor = 2; factor * factor <= num; factor++)
if (num % factor == 0)
return 1;
return 0;
}

#include <stdio.h>
int main(void)
{
for (int i = 0; i < 1000; i++)
if (is_prime(i))
printf("%d", i) ;
return 0;
}

1>------ Build started: Project: Test, Configuration: Debug Win32 ------
1>Compiling...
1>test.c
1>c\:visual studio 2005\projects\test\test\test.c(3) : error C2061:
syntax error : identifier 'is_prime'
1>c\:visual studio 2005\projects\test\test\test.c(3) : error C2059:
syntax error : ';'
1>c\:visual studio 2005\projects\test\test\test.c(3) : error C2059:
syntax error : 'type'
1>c\:visual studio 2005\projects\test\test\test.c(15) : error C2143:
syntax error : missing ';' before 'type'
1>c\:visual studio 2005\projects\test\test\test.c(15) : error C2143:
syntax error : missing ';' before 'type'
1>c\:visual studio 2005\projects\test\test\test.c(15) : error C2143:
syntax error : missing ')' before 'type'
1>c\:visual studio 2005\projects\test\test\test.c(15) : error C2143:
syntax error : missing ';' before 'type'
1>c\:visual studio 2005\projects\test\test\test.c(15) : error C2065: 'i'
: undeclared identifier
1>c\:visual studio 2005\projects\test\test\test.c(15) : warning C4552:
'<' : operator has no effect; expected operator with side-effect
1>c\:visual studio 2005\projects\test\test\test.c(15) : error C2059:
syntax error : ')'
1>c\:visual studio 2005\projects\test\test\test.c(16) : error C2143:
syntax error : missing ';' before 'if'
1>c\:visual studio 2005\projects\test\test\test.c(16) : warning C4013:
'is_prime' undefined; assuming extern returning int
1>Test - 10 error(s), 2 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

on changing the return type of is_prime to int and a further
change(declaration) in main ..i.e

int main(void)
{
int i; /*declared here*/
for (i=0;i<1000;i++)
if (is_prime(i))
printf("%d ",i);
return 0;
}

here is the output:-
0 1 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32 33 34 35 36
38 39 40 42 44 45 46 48 49 50 51 52 54 55 56 57 58 60 62 63 64 65 66 68
69 70 72 74 75 76 77 78 80 81 82 84 85 86 87 88 90 91 92 93 94 95 96 98
99 100
...the rest of the output snipped...

so basically it just doesn't work!
Is this something to do with the compiler..i.e. the "bool" return type
is addressed differently on differently on different compilers??

This is what happens if i let the return type as bool!

1>------ Build started: Project: Test, Configuration: Debug Win32 ------
1>Compiling...
1>test.c
1>c:\visual studio 2005\projects\test\test\test.c(3) : error C2061:
syntax error : identifier 'is_prime'
1>c:\visual studio 2005\projects\test\test\test.c(3) : error C2059:
syntax error : ';'
1>c:\visual studio 2005\projects\test\test\test.c(3) : error C2059:
syntax error : 'type'
1>c:\visual studio 2005\projects\test\test\test.c(17) : warning C4013:
'is_prime' undefined; assuming extern returning int
1>Test - 3 error(s), 1 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

 

[lovecreatesbea...]

Ian Collins said:

(e-mail address removed) wrote:
[C++ code]
This group deals with C, not C++. Go ask this in comp.lang.c++.

Excuse me, but with the addition of an include of <stdbool.h> the code
is legal C.True, although it's a legal C for which hardly anyone has a conforming

compiler. Nevertheless, the way he's compiling it indicates pretty clearly
that he thinks he's using C++. Why else would he name his source file
a.cpp?

Thank you.

Following is a revised one. I droped the filename. Could you please
talk about the logic and correctness of the code?

/*return 0 if num is a prime number otherwise 1*/
int is_prime(int num)
{
int factor;
if (num < 2) return 1;
for (factor = 2; factor * factor <= num; factor++)
if (num % factor == 0)
return 1;
return 0;
}

 

[lovecreatesbea...]

on changing the return type of is_prime to int and a further
change(declaration) in main ..i.e

int main(void)
{
int i; /*declared here*/
for (i=0;i<1000;i++)
if (is_prime(i))

then you should change change the invocation statement as following:

if (is_prime(i) == 0)
or
if (!is_prime(i))

see the function specification:
/*return 0 if num is a prime number otherwise 1*/
int is_prime(int num);

 

[Kelly]

then you should change change the invocation statement as following:

if (is_prime(i) == 0)
or
if (!is_prime(i))

Why on earth!!

see the function specification:
/*return 0 if num is a prime number otherwise 1*/
int is_prime(int num);



No

check your code,its pretty simple to compile it run it(and to post the
actual output)!
i hope you will notice that your *bugged* code produces every number
except primes!!

check your logic again..its not that tough!

 

[santosh]

Ian Collins said:

Harald van D?k wrote:
(e-mail address removed) wrote:

[C++ code]

This group deals with C, not C++. Go ask this in comp.lang.c++.

Excuse me, but with the addition of an include of <stdbool.h> the code
is legal C.True, although it's a legal C for which hardly anyone has a conforming

compiler. Nevertheless, the way he's compiling it indicates pretty clearly
that he thinks he's using C++. Why else would he name his source file
a.cpp?

Thank you.

Following is a revised one. I droped the filename. Could you please
talk about the logic and correctness of the code?

/*return 0 if num is a prime number otherwise 1*/
int is_prime(int num)
{
int factor;
if (num < 2) return 1;
for (factor = 2; factor * factor <= num; factor++)
if (num % factor == 0)
return 1;
return 0;
}

For alternative methods see the following page:

<http://en.wikipedia.org/wiki/Primality_testing>
<http://mathworld.wolfram.com/PrimalityTest.html>
<http://www-math.mit.edu/phase2/UJM/vol1/DORSEY-F.PDF>

 

[Ian Collins]

then you should change change the invocation statement as following:

if (is_prime(i) == 0)
or
if (!is_prime(i))

Why? That's completely counter intuitive.

 

[BRG]

(e-mail address removed) wrote:

[snip]

then you should change change the invocation statement as following:

if (is_prime(i) == 0)
or
if (!is_prime(i))

see the function specification:
/*return 0 if num is a prime number otherwise 1*/
int is_prime(int num);



No

Kelly is right, your program identifies composite numbers, not primes,
because your function specification is poor for use in C code.

Unless you have very good reasons for doing otherwise, it makes sense to
adopt conventions that are built into the language rather than ones that
are in conflict with these built-in conventions.

In C it is normal to associate the zero (0) with false and non-zero (or
1) with true. Hence when a function called is_prime() returns a value of
1 many C programmers will reasonably assume that the statement "is
prime" is true for the input value used.

In consequence your use of the opposite convention is both unusual and
misleading when combined with the name you have chosen for your function.

You should either invert the true/false convention in your function
specification (and code) or alternatively rename your function to either
is_not_prime() or is_composite().

Brian Gladman

 

[mark_bluemel]

Hello experts,

The following is_prime function doesn't call a library function and it
works.

For some very odd value of "works"...

Does it have bugs like "integer overflow": int factor; factor * factor,
or it's not single entry/exit, or others... Thank you.

Apart from not doing the appropriate thing, do you mean?

/*return 0 if num is a prime number otherwise 1*/

In C terms you are saying "is_prime(x) returns FALSE if x is a prime
number".
Are you clear on that?
Did you really mean it?

bool is_prime(int num)
{
int factor;
if (num < 2) return 1;
for (factor = 2; factor * factor <= num; factor++)
if (num % factor == 0)
return 1;
return 0;

}
#include <stdio.h>
int main(void)
{
for (int i = 0; i < 1000; i++)
if (is_prime(i))

Remember is_prime() returns FALSE for prime values of i... So this will
show all non-primes...

printf("%d", i) ;

No space or newline, so your results are concatenated into one large
string.

return 0;

}/*
Run: C:\MinGW\bin\mingw32-make.exe
gcc -ansi -pedantic -Wall -W -c -o a.o a.cpp
gcc a.o b.o -o a.out

Press the Enter key to return to Source Insight...

Run: D:\working\c\a.out
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

You can't have got this output from that program. For a start, your
program as posted doesn't put any spaces in its output...

What are you trying to prove here?

 

[CBFalconer]

.... snip ...

Following is a revised one. I droped the filename. Could you
please talk about the logic and correctness of the code?

/*return 0 if num is a prime number otherwise 1*/
int is_prime(int num)
{
int factor;
if (num < 2) return 1;
for (factor = 2; factor * factor <= num; factor++)
if (num % factor == 0)
return 1;
return 0;
}

Try the following minimal modifications. Try to post compilable
code, not snippets.

#include <stdio.h>

/* return 1 if num is a prime number otherwise 0 */
int is_prime(int num) {
int factor;

if (2 == num) return 1;
if (2 > num) return 0;
if (0 == num % 2) return 0;
for (factor = 3; factor * factor <= num; factor += 2)
if (num % factor == 0)
return 0;
return 1;
}

int main(void) {
int i, l;

for (i = l = 0; i < 1000; i++) {
if (is_prime(i)) {
if (72 < (l += printf("%4d ", i))) {
putchar('\n');
l = 0;
}
}
}
return 0;
}

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Richard Heathfield]

(e-mail address removed) said:

Following is a revised one. I droped the filename. Could you please
talk about the logic and correctness of the code?

/*return 0 if num is a prime number otherwise 1*/
int is_prime(int num)

It would make far more sense for a function named is_prime to return 0
(false) if the number is *not* prime, and non-zero (true) - e.g. 1 - if it
*is* prime.

Otherwise, your code would read like this:

if(is_prime(n))
{
printf("%d is not prime!\n", n);
}

which reads rather oddly, does it not?

Also, since primes are by definition positive, I recommend using an unsigned
integer type, to increase the size of the domain over which the function
operates.

Still, for now, let's go with what you've got. We consider the case where
num = 2.

{
int factor;
if (num < 2) return 1;

num is not less than 2, so we don't return at this point.

for (factor = 2; factor * factor <= num; factor++)

factor is 2 to start off with.

if (num % factor == 0)
return 1;

2 % 2 is 0, so your function returns 1 which means, according to your
documentation, that 2 is not prime.

I conclude that the code is incorrect.

 

[Guest]

(e-mail address removed) said:
Still, for now, let's go with what you've got. We consider the case where
num = 2.


num is not less than 2, so we don't return at this point.


factor is 2 to start off with.

So factor * factor > num, so the loop is skipped.