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