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

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

[e-mail] wrote:

[C++ code]

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

[Ian Collins]

Harald van Dijk wrote:

[e-mail] 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.hthe code
is legal C.

--
Ian Collins.

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

Ian Collins wrote:

Harald van Dijk wrote:

[e-mail] 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.hthe 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]

[e-mail] wrote:

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.

--
Ian Collins.

[Richard Heathfield]

Ian Collins said:

Harald van D?k wrote:

>[e-mail] 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.hthe 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?

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Ian Collins]

Harald van Dijk wrote:

Ian Collins wrote:

>>Harald van Dijk wrote:

>>>[e-mail] 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.hthe 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.

--
Ian Collins.

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

Ian Collins wrote:

Harald van Dijk wrote:

Ian Collins wrote:

>Harald van Dijk wrote:

[e-mail] 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.hthe 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.hwould 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.hand declarations in for statements.

[Ian Collins]

Harald van Dijk wrote:

Ian Collins wrote:

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

He didn't leave out <stdio.h>, and adding <stdbool.hwould 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.hand declarations in for statements.

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

--
Ian Collins.

[Kelly]

[e-mail] wrote:

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

On 1ÔÂ24ÈÕ, ÏÂÎç4ʱ12·Ö, Richard Heathfield
<[e-mail]:

Ian Collins said:

Harald van D?k wrote:

[e-mail] 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.hthe 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 1ÔÂ24ÈÕ, ÏÂÎç4ʱ30·Ö, Kelly <[e-mail]:

[e-mail] wrote:

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;

<snip>

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);

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!

No

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!

[Kelly]

[e-mail] wrote:

>
On 1月24日, 下�4时30分, Kelly <[e-mail]:

>[e-mail] wrote:
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))

Why on earth!!

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

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

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]

[e-mail] wrote:

On 1ÔÂ24ÈÕ, ÏÂÎç4ʱ12·Ö, Richard Heathfield
<[e-mail]:

Ian Collins said:

Harald van D?k wrote:
>[e-mail] 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.hthe 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]

[e-mail] wrote:

>
On 1ÔÂ24ÈÕ, ÏÂÎç4ʱ30·Ö, Kelly <[e-mail]:

>>[e-mail] wrote:

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

<snip>

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

Why? That's completely counter intuitive.

--
Ian Collins.

[BRG]

[e-mail] 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);

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

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]

On 24 Jan, 07:31, "[e-mail]"
<[e-mail]:

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?

[Richard Heathfield]

[e-mail] said:

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

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.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

Richard Heathfield wrote:

[e-mail] said:
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.

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

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.

[Richard Heathfield]

Harald van D?k said:

Richard Heathfield wrote:

>[e-mail] said:
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.

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

Oh, good spot. My apologies to the OP.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Kelly]

[e-mail] wrote:

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.

This will print primes,rest is just fine until u take care of the
limits that your particular compiler imposes on the limit
of int,check <limits.h>
so that factor*factor doesn't overflow the limit
or else just use unsigned long type
#include <stdio.h>
#define MAX 1000

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

int main(void)
{
int i;
for (i=0;i<MAX;i++)
if (is_prime(i))
printf("%d\n",i);
return 0;
}

[Richard Heathfield]

Kelly said:

<snip>

>
[...] take care of the
limits that your particular compiler imposes on the limit
of int,check <limits.h>
so that factor*factor doesn't overflow the limit

Or, knowing that factor >= 2, you can do this: factor <= num / factor

Or better still, you can do this:

max = sqrt(num);
for(factor = 2; factor <= max; factor++)

which removes the in-loop calculation completely and therefore removes the
possibility of overflow in that calculation (and yes, more optimisation
work remains to be done, but this thread isn't about optimisation).

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[CBFalconer]

"[e-mail]" wrote:

>

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