i'm sure this must be trivial, remember i'm learning ... program included

[G G]

this is an exercise from Deitel and Deitel chapter 5 on prime number.
the problem suggest that there is a speed increase if only the square root
of the number of comparisons are made to determine if a number is
prime or not.

There is, but in my program i noticed that it found less primes. So i must
have a logic error, in the code, right? it should find the same number of
primes, just faster. i'm hoping your skill eyes can point out my error. the
only thing changed is the number of comparisons made to determine if the
number is prime,

i created two functions, isThisAPrime (int number), and
isThisAPrimeSqrt (int number)
so that if you need to test you only have to change "isThisAPrime...."
to switch to the other function.

The total number, of primes, is different between these two functions. they
should not be. the total number of primes found should be the same. the
total number of primes maintained by variable numberOfPrimes in the
program.

Thanks everyone,

g.

-----------------------------------------------------------------

/* main.c */

/* exercise5_27.c */

/*
* (Prime Numbers)
* An integer is said to be prime if it’s divisible by
* only 1 and itself. For ex- ample, 2, 3, 5 and 7 are
* prime, but 4, 6, 8 and 9 are not.
*
* a) Write a function that determines if a number is prime.
* b) Use this function in a program that determines and
* prints all the prime numbers between 1 and 10,000. How
* many of these 10,000 numbers do you really have to test
* before being sure that you have found all the primes?
* c) Initially you might think that n/2 is the upper limit
* for which you must test to see if a number is prime,
* but you need go only as high as the square root of n.
* Why? Rewrite the program, and run it both ways. Estimate
* the performance improvement.
*
* written by gdotone
*/

#include <stdio.h>
#include <math.h>

#define LASTNUMBER 1000000 /* changed to note the speed difference */
#define NUMBEROFCOLUMNS 6 /* number of columns per row printed out */

/* prototypes */
int isThisAPrime ( int number ); /* determines if number is prime */
int isThisAPrimeSqrt (int number ); /* determines if number is prime
only checking sqrt(number) divisible */

/*********************** main() ********************************/

int main ( int argc, char *argv[] )
{
int numberOfPrimes = 0; /* used to create number of column rows */
/* and count the number of primes found */

for (int i = 1; i < LASTNUMBER; i++ )
{
if ( isThisAPrime(i) ) /* change to isThisAPrimeSqrt to use other()*/
{
printf("%8d\t", i );
numberOfPrimes++;
if ( ( numberOfPrimes % NUMBEROFCOLUMNS ) == 0 )
printf ("\n");

} /*end if ( isThisA ... ) */

} /* end for ( int i ... ) */

printf("\n %d \n\n", numberOfPrimes);
return 0;

} /* end main () */

/*********************** inThisAPrime() *************************/
int isThisAPrime ( int number )
{
if ( (number == 1) || (number == 5) )
return 1;
else if ( ( (number%2) == 0 ) || ( (number%5) == 0 ) )
return 0;
else
{
for ( int i = 2; i < number; i++ ) /* i < number */
if ( (number % i) == 0 )
return 0;

} /* end else */

return 1;

} /* end isThisAPrime ( int ...) */

/********** isThisAPrimeSqrt() with sqrt(number) used *********/
int isThisAPrimeSqrt ( int number )
{
if ( (number == 1) || (number == 5) )
return 1;
else if ( ( (number%2) == 0 ) || ( (number%5) == 0 ) )
return 0;
else
{
for ( int i = 2; i < sqrt(number); i++ ) /* i < sqrt(number) */
if ( (number % i) == 0 )
return 0;

} /* end else */

return 1;

} /* end isThisAPrime ( int ...) */

 

[Ben Bacarisse]

this is an exercise from Deitel and Deitel chapter 5 on prime number.
the problem suggest that there is a speed increase if only the square root
of the number of comparisons are made to determine if a number is
prime or not.

There is, but in my program i noticed that it found less primes.

It finds more, not fewer. Well, it prints more numbers -- some of which
are not prime.

So i must
have a logic error, in the code, right?

Yes. In fact both functions have logic errors. In addition to the
problem you are posting about, neither lists 2, which is a prime, and
both list 1, which is not.

it should find the same number of
primes, just faster. i'm hoping your skill eyes can point out my error. the
only thing changed is the number of comparisons made to determine if the
number is prime,

i created two functions, isThisAPrime (int number), and
isThisAPrimeSqrt (int number)
so that if you need to test you only have to change "isThisAPrime...."
to switch to the other function.

The total number, of primes, is different between these two functions. they
should not be. the total number of primes found should be the same. the
total number of primes maintained by variable numberOfPrimes in the
program.

Rather just say "here's the problem" I think you'd get more joy finding
it for yourself. It's not hard. You could write a program prints a
number only is isThisAPrime(n) != isThisAPrimeSqrt(n). Look at the
first few numbers -- they all have a very particular property that
should lead you to the problem right away. It might be even more
obvious is you removed the special cases from the functions -- the code
that treats multiples of 2 and 5 separately.

/*********************** inThisAPrime() *************************/
int isThisAPrime ( int number )
{
if ( (number == 1) || (number == 5) )
return 1;
else if ( ( (number%2) == 0 ) || ( (number%5) == 0 ) )
return 0;

1 is not prime (basically by conventional agreement), so you should
remove that special case, but why treat 2 and 5 as special? Why not 2
and 3, or 2, 3 and 5? At the very least, this is the kind of thing that
needs a comment. You have lots of comments, but none of them help me
understand your code -- I know where functions start and where code
blocks end and so on, but I don't know why 5 is special to you.

else
{
for ( int i = 2; i < number; i++ ) /* i < number */

Having tested for divisibility by 2, there is no need to do it again.
Also, while you need to test for divisibility by 3, do you need to test
for divisibility by 4? Or by 6? Or 8?

if ( (number % i) == 0 )
return 0;

} /* end else */

return 1;

} /* end isThisAPrime ( int ...) */

/********** isThisAPrimeSqrt() with sqrt(number) used *********/
int isThisAPrimeSqrt ( int number )
{
if ( (number == 1) || (number == 5) )
return 1;
else if ( ( (number%2) == 0 ) || ( (number%5) == 0 ) )
return 0;
else
{
for ( int i = 2; i < sqrt(number); i++ ) /* i < sqrt(number) */
if ( (number % i) == 0 )
return 0;

} /* end else */

return 1;

} /* end isThisAPrime ( int ...) */

No, that comment is wrong! That's one reason I never use such comments.

By the way, a small point, but I prefer to name true/false function by
the condition of them being true, not as a question. So I'd call the
function thisIsAPrime (actually I'd call it is_prime, because the "this"
and the "a" are redundant and I'm old-fashioned about camelCaseNames).
The effect is to make conditions read more naturally: if (is_prime(n))
and while (is_prime(x)) ... and so one. It's a matter of style so it is
ultimately a personal choice (unless you work somewhere with a house
style).

 

[Keith Thompson]

this is an exercise from Deitel and Deitel chapter 5 on prime number.
the problem suggest that there is a speed increase if only the square root
of the number of comparisons are made to determine if a number is
prime or not.

There is, but in my program i noticed that it found less primes. So i must
have a logic error, in the code, right? it should find the same number of
primes, just faster. i'm hoping your skill eyes can point out my error. the
only thing changed is the number of comparisons made to determine if the
number is prime,

i created two functions, isThisAPrime (int number), and
isThisAPrimeSqrt (int number)
so that if you need to test you only have to change "isThisAPrime...."
to switch to the other function.

The total number, of primes, is different between these two functions. they
should not be. the total number of primes found should be the same. the
total number of primes maintained by variable numberOfPrimes in the
program.

Thanks everyone,

g.

-----------------------------------------------------------------

/* main.c */

/* exercise5_27.c */

/*
* (Prime Numbers)
* An integer is said to be prime if it’s divisible by
* only 1 and itself. For ex- ample, 2, 3, 5 and 7 are
* prime, but 4, 6, 8 and 9 are not.
*
* a) Write a function that determines if a number is prime.
* b) Use this function in a program that determines and
* prints all the prime numbers between 1 and 10,000. How
* many of these 10,000 numbers do you really have to test
* before being sure that you have found all the primes?
* c) Initially you might think that n/2 is the upper limit
* for which you must test to see if a number is prime,
* but you need go only as high as the square root of n.
* Why? Rewrite the program, and run it both ways. Estimate
* the performance improvement.
*
* written by gdotone
*/

#include <stdio.h>
#include <math.h>

#define LASTNUMBER 1000000 /* changed to note the speed difference */
#define NUMBEROFCOLUMNS 6 /* number of columns per row printed out */

[prototypes and main program snipped]

/*********************** inThisAPrime() *************************/
int isThisAPrime ( int number )
{
if ( (number == 1) || (number == 5) )
return 1;
else if ( ( (number%2) == 0 ) || ( (number%5) == 0 ) )
return 0;
else
{
for ( int i = 2; i < number; i++ ) /* i < number */
if ( (number % i) == 0 )
return 0;

} /* end else */

return 1;

} /* end isThisAPrime ( int ...) */

Why do you have special-case tests for 2 and 5? The for loop by itself
should be enough. If you're thinking that you can save time by avoiding
the loop in some cases, then (a) you're very likely mistaken, (b) even
if you're right the performance improvement is likely to be trivial
(make it right before you make it fast, and *measure*), and (c) you'll
get more "bang for your buck" by testing 2 and 3 rather than 2 and 5.

Your for loop tests whether `number` is a multiple of 2, but it never
will be, since you've already eliminated even numbers.

And 1 is not generally considered to be a prime number, for mathematical
reasons going back at least to Euclid.

/********** isThisAPrimeSqrt() with sqrt(number) used *********/
int isThisAPrimeSqrt ( int number )
{
if ( (number == 1) || (number == 5) )
return 1;
else if ( ( (number%2) == 0 ) || ( (number%5) == 0 ) )
return 0;
else
{
for ( int i = 2; i < sqrt(number); i++ ) /* i < sqrt(number) */
if ( (number % i) == 0 )
return 0;

} /* end else */

return 1;

} /* end isThisAPrime ( int ...) */

Same comments about 1, 2, and 5.

Take a close look at your for loop, and consider what it will do with
`number == 49`. It will iterate over potential factors starting with 2,
considering only number that are *less than* sqrt(49) -- which means it
won't test 7. The prime numbers this misses are squares of primes other
than 2 and 5. You want `i <= sqrt(number)`, not `i < sqrt(number)`.

That should solve the problem you're seeing, but there are some other
issues. The sqrt() function operates on floating-point numbers, which
means (a) it's likely to be more expensive than integer operations
(depending on the system), and (b) it's potentially imprecise. It's
likely that sqrt() will yield an exact result for an exact integer
square (for example, sqrt(49) will probably yield exactly 7.0), but
that's not absolutely guaranteed.

And you're computing sqrt(number) for every iteration of the loop --
even though its value never changes. That's expensive.

If you want to use sqrt(), you should compute it once at the top of the
loop:

const int sqrt_n = sqrt(number); /* Note: This converts number from
int to float and then converts
the result back from float to
int */
for (int i = 2; i <= sqrt_n); i ++)
...

But there's a more reliable way to do the comparison, that avoids any
floating-point calculations:

for (int i = 2; i * i <= number; i ++)

This does perform a multiplication on each iteration, whereas the
previous version computes sqrt() only once. It's not clear which will
be faster, but the version that does only integer arithmetic is
conceptually simpler.

 

[G G]

thanks Ben, thanks Keith

yes, this a cool thought, "...write a program prints a
number only is isThisAPrime(n) != isThisAPrimeSqrt(n)..."

will do.

} /* end isThisAPrime ( int ...) */

No, that comment is wrong! That's one reason I never use such comments.

i cut and pasted, i should be more careful.

thanks again guys, i really never would have seen those errors.

g.

 

[Malcolm McLean]

this is an exercise from Deitel and Deitel chapter 5 on prime number.
the problem suggest that there is a speed increase if only the square root
of the number of comparisons are made to determine if a number is
prime or not.

There is, but in my program i noticed that it found less primes. So i must
have a logic error, in the code, right? it should find the same number of
primes, just faster.

Others have commented on the program itself.

I'll say that your approach is right. When you've got a slow and easy way
of calculating a value, and a fast and tricky way, write the slow and easy
function first and check it.
Then write the fast way, and write an automated test to test for maybe
a minute (it depends on how slow the slow method is) on different values.
Normally this test is quite easy to write - you just set the input to
different random numbers. You usually want to test for special cases like 0,
1, -1 and so on. That reveals any problems.

You then need to get to the root of any bugs. Don't disguise them or
code round them. Find out why the function is wrong, and fix the problem
at source.

 

[G G]

thanks Ben, thanks Keith

yes, this a cool thought, "...write a program prints a
number only is isThisAPrime(n) != isThisAPrimeSqrt(n)..."
will do.

Ben suggestion implemented,
Keith I found that I needed to add one, 1, to sqrt(number) for the loop
to execute the correct number of times. I did pull that calculation out
of the loop control for statement, thanks.

this seems to work fine. well, no, no, let me say that it finds no values
that are different in it's quest to tell if the same number it prime ...
yeah, ok, ok, i know that's a big difference
from being correct.

i do need to tighten up on my comments in the program. so, i really
appreciate any and all comment about comments, program clarity.
my thought was yes, true, no, false in my head i'm trying to think either
because some code, in the books i'm reading, think yes, no, in those if
comparisons.
so i thought isThisAPrime (number) read well. hey, i can change that
thought though. is_prime(x) is fine. my end goal is to learn and write
code that you guys read with professional ease. i'm a long way from that
right now...

please tell me if my style is out there, too far from the norm.

thanks again,
g.
ben's suggestion program below.

oh, yeah, the hints and direction to thought is much better than just
telling me the answer. i'm learning more, well it seems that way. i'm
sure there will come a time where i just don't understand.

----------------------------------------------------------


/* main.c */

/* exercise5_27.c */

/*
* (Prime Numbers)
* This program is base on an exercise found in Deitel and Deitel
* chapter 5.
*
**** This program is an incite, passed on by Ben Bacarisse of the *****
**** Comp.lang.c Group on Google Group, to solve a mistake of ****
**** which I had in a earlier post to comp.lang.c. This program *****
**** compares the output of two function that are finding prime *****
**** numbers. The program prints the number at which there may****
**** disagreement between the functions *****
*
* written by gdotone and with insite for corrections of the
* original post on comp.lang.c from Ben B., and Keith T.
* Ben and Keith gave great insites.
*/

#include <stdio.h>
#include <math.h>

#define LASTNUMBER 1000000 /* change to note the speed diff */
#define NUMBEROFCOLUMNS 6

/* prototypes */
int isThisAPrime ( int number ); /* determines if number is prime */
int isThisAPrimeWithSqrt (int number ); /* determines if number is prime
only checking sqrt(number) + 1
divisible */

/*********************** main() ********************************/

int main ( int argc, char *argv[] )
{
int total_diff_numbers = 0; /* total of numbers that are different */

/* 1 not prime by definition */
for (int number = 2; number < LASTNUMBER; number++ )
{
if ( isThisAPrime(number) != isThisAPrimeWithSqrt(number) )
{
printf( "%8d\t", number );
total_diff_numbers++;
if ( ( total_diff_numbers % NUMBEROFCOLUMNS ) == 0 )
printf ("\n");

} /*end if ( isThisA ... ) */

} /* end for ( int i ... ) */

printf("\n %d \n\n", total_diff_numbers );
return 0;

} /* end main () */


/*********************** inThisAPrime() *************************/

int isThisAPrime ( int number )
{
if ( number == 2 )
return 1;
else
{
for ( int i = 2; i < number; i++ )
{
if ( (number % i) == 0 )
return 0;
}
} /* end else */

return 1;

} /* end isThisAPrime ( int ...) */


/**** isThisAPrime function with sqrt(number) used ******/

int isThisAPrimeWithSqrt ( int number )
{
int sqRootOfNumber = (int) sqrt(number); /* is used in control loop */
/* cast to integer */

if ( number == 2 )
return 1;
else
{
for ( int i = 2; i < sqRootOfNumber + 1; i++ )
if ( (number % i) == 0 )
return 0;

} /* end else */

return 1;

} /* end isThisAPrimeWithSqrt ( int ...) */

 

[G G]

One smal nit here, it isn't that you want the sqrt+1, but that you want
the loop to go from 2 up to *and including* sqrt(n), thus the loop
really should be

 

[G G]

you are absolutely right Keith told me that too.

 

[James Kuyper]

One smal nit here, it isn't that you want the sqrt+1, but that you want
the loop to go from 2 up to *and including* sqrt(n), thus the loop
really should be

for ( int i = 2; i <= sqRootOfNumber; i++)
not
for ( int i = 2; i < sqRootOfNumber+1; i++)

Yes, they do the same thing, but the first shows the intent better.

Due to floating point roundoff, that's not necessarily sufficient.
For sufficiently small squares of integer values, sqrt() is likely to
return the exact square root, but it's safer not to rely upon that; it's
certainly not true for larger numbers.

 

[Eric Sosman]

Due to floating point roundoff, that's not necessarily sufficient.
For sufficiently small squares of integer values, sqrt() is likely to
return the exact square root, but it's safer not to rely upon that; it's
certainly not true for larger numbers.

... which leads to the Real Way of doing the square-root
test. If `i' is less than sqrt(number), then `number / i' is
greater than `i'. And if `i' is greater than sqrt(number), then
`number / i' is less than `i'. *And* when you ask the computer
for either of `number % i' or `number / i', the computer almost
surely calculates the other one as a by-product. *And* a smart
optimizer will almost certainly notice this, so when it sees both
`number % i' and `number / i' (for the same `i' and `number'), it
will very likely perform only one division, retaining both outputs
instead of discarding one of them.

Calculating and re-calculating and re-re-calculating sqrt(number)
is silly to begin with: It'd be better to calculate it once and use
the calculated root to stop the loop. But even better would be to
calculate it *never* and use the condition `i / number <= i' to
stop the loop; it's very probably "free."

 

[glen herrmannsfeldt]

On 9/21/13 8:38 PM, James Kuyper wrote:
(snip)
(snip)
Yes, there is a posibility of a round off error in the sqrt, but that
should be taken care of on the line that does the sqrt.

Now, for n representable by a 32 bit interger, I would actually expect
sqrt to return the exact answer, as it isn't that hard for the library
to get this right. If you wanted to add a bit of a guardband, the place
to do it is adjusting the result of sqrt before converting it to an
integer, adding some small fraction to affect some rounding.

I suppose, but increasing by one isn't all that expensive.
Since testing one more divisor still should give the right
result, that is probably what I would do.

-- glen

 

[Tim Rentsch]

[how to limit 'i' to no more than the square root of 'number']

But there's a more reliable way to do the comparison, that avoids
any floating-point calculations:

for (int i = 2; i * i <= number; i ++)

This does perform a multiplication on each iteration, whereas the
previous version computes sqrt() only once. It's not clear which
will be faster, but the version that does only integer arithmetic
is conceptually simpler.

If one is being careful, it's important not to write tests
this way because of bad results or undefined behavior when
'number' is very large. For example, on an implementation
where INT_MAX is 2147483647, suppose the number being tested
is INT_MAX, which also is prime in this case. When 'i' is
46340, i*i == 2147395600, which is less than INT_MAX, but
when 'i' is 46341, i*i == 2147488281, which is an overflow,
ie, undefined behavior. So to be completely reliable a
certain amount of care needs to be taken in how the test is
expressed so it doesn't do the wrong thing in such cases.