Bugs in an is_prime() implementation

Discussion in 'C Programming' started by lovecreatesbea...@gmail.com, Jan 24, 2007.

  1. Guest

    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...
    */
     
    , Jan 24, 2007
    #1
    1. Advertising

  2. wrote:
    > [C++ code]


    This group deals with C, not C++. Go ask this in comp.lang.c++.
     
    =?utf-8?B?SGFyYWxkIHZhbiBExLNr?=, Jan 24, 2007
    #2
    1. Advertising

  3. Ian Collins Guest

    Harald van Dijk wrote:
    > 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.

    --
    Ian Collins.
     
    Ian Collins, Jan 24, 2007
    #3
  4. Ian Collins wrote:
    > Harald van Dijk wrote:
    > > 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.
     
    =?utf-8?B?SGFyYWxkIHZhbiBExLNr?=, Jan 24, 2007
    #4
  5. Ian Collins Guest

    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.
     
    Ian Collins, Jan 24, 2007
    #5
  6. Ian Collins said:

    > Harald van D?k wrote:
    >> 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?

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at the above domain, - www.
     
    Richard Heathfield, Jan 24, 2007
    #6
  7. Ian Collins Guest

    Harald van Dijk wrote:
    > Ian Collins wrote:
    >
    >>Harald van Dijk wrote:
    >>
    >>> 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.

    --
    Ian Collins.
     
    Ian Collins, Jan 24, 2007
    #7
  8. Ian Collins wrote:
    > Harald van Dijk wrote:
    > > Ian Collins wrote:
    > >
    > >>Harald van Dijk wrote:
    > >>
    > >>> 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.
     
    =?utf-8?B?SGFyYWxkIHZhbiBExLNr?=, Jan 24, 2007
    #8
  9. Ian Collins Guest

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

    --
    Ian Collins.
     
    Ian Collins, Jan 24, 2007
    #9
  10. Kelly Guest

    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 ==========
     
    Kelly, Jan 24, 2007
    #10
  11. Guest

    On 1ÔÂ24ÈÕ, ÏÂÎç4ʱ12·Ö, Richard Heathfield
    <> wrote:
    > Ian Collins said:
    >
    > > Harald van D?k wrote:
    > >> 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;
    }
     
    , Jan 24, 2007
    #11
  12. Guest

    On 1ÔÂ24ÈÕ, ÏÂÎç4ʱ30·Ö, Kelly <> wrote:
    > 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!
     
    , Jan 24, 2007
    #12
  13. Kelly Guest

    wrote:
    >
    > On 1月24æ—¥, 下åˆ4æ—¶30分, Kelly <> wrote:
    >> 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!
     
    Kelly, Jan 24, 2007
    #13
  14. santosh Guest

    wrote:
    > On 1ÔÂ24ÈÕ, ÏÂÎç4ʱ12·Ö, Richard Heathfield
    > <> wrote:
    > > Ian Collins said:
    > >
    > > > Harald van D?k wrote:
    > > >> 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>
     
    santosh, Jan 24, 2007
    #14
  15. Ian Collins Guest

    wrote:
    >
    > On 1ÔÂ24ÈÕ, ÏÂÎç4ʱ30·Ö, Kelly <> wrote:
    >
    >> 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.
     
    Ian Collins, Jan 24, 2007
    #15
  16. BRG Guest

    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
     
    BRG, Jan 24, 2007
    #16
  17. Guest

    On 24 Jan, 07:31, ""
    <> wrote:
    > 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?
     
    , Jan 24, 2007
    #17
  18. CBFalconer Guest

    "" 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
     
    CBFalconer, Jan 24, 2007
    #18
  19. 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.
     
    Richard Heathfield, Jan 24, 2007
    #19
  20. Richard Heathfield wrote:
    > 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.
     
    =?utf-8?B?SGFyYWxkIHZhbiBExLNr?=, Jan 24, 2007
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?TkdN?=
    Replies:
    1
    Views:
    733
  2. Michael Tsang
    Replies:
    32
    Views:
    1,127
    Richard Bos
    Mar 1, 2010
  3. Michael Tsang
    Replies:
    54
    Views:
    1,208
    Phil Carmody
    Mar 30, 2010
  4. sanket
    Replies:
    7
    Views:
    1,022
    Tsung
    Nov 3, 2011
  5. Josef 'Jupp' Schugt

    Still use 'ruby-bugs' for Ruby bugs?

    Josef 'Jupp' Schugt, Nov 4, 2004, in forum: Ruby
    Replies:
    2
    Views:
    165
    Tom Copeland
    Nov 4, 2004
Loading...

Share This Page