English Deutsch Français Italiano Español Português 繁體中文 Bahasa Indonesia Tiếng Việt ภาษาไทย
All categories

2 answers

Sieve of Eratosthenes. No warranty, check the pseudo code at wikipedia
// ***********************************************************************
// * *
// * sieveOfEratosthenes *
// * *
// * *
// * This program shows an example of work that may be considered *
// * excellent in your computer science program. It calculates a range *
// * of prime numbers from a starting point to an ending point, using *
// * the standard "tricks" to save time: *
// * *
// * *
// * * Each prime found can be recorded in the famous "sieve" of *
// * Eratosthenes, and to test primality, we can just divide *
// * candidates by sieve members...until the numbers in the *
// * sieve run out. *
// * *
// * * If the sieve does not contain all prime numbers up to n-2 *
// * where n is the (odd) candidate then starting after m+2, *
// * where m is the last element of the sieve (or 3 when the *
// * sieve is empty), we can divide the candidate by odd numbers *
// * up to and including floor(n/2) (the integer part of the *
// * candidate n divided by 2). *
// * *
// * *
// ***********************************************************************

#include
#include
#include

// ***** Constants and macros *******************************************

#define SIEVESIZE (1000)
#define SYNTAX_REMINDER \
("sieveOfEratosthenes []")
#define IS_FACTOR( n, m ) ( (n) % (m) == 0 )
#define MAX( x, y ) ( (x) > (y) ? (x) : (y) )

// ***** Tools ***********************************************************

// -----------------------------------------------------------------------
// Convert character to its numeric form
//
//
int char2Number( char chrInChar )
{
int intInCharValue = ( int )chrInChar;
int intZeroValue = ( int )'0';
if ( intInCharValue < intZeroValue
||
intInCharValue > ( int )'9' ) return -1;
return intInCharValue - intZeroValue;
}

// -----------------------------------------------------------------------
// Convert a string containing an unsigned number to its value: return
// true (-1) on success or false (0) on failure
//
//
// This function returns false when the number's value overflows, but in
// this case, its reference parameter intValue is still returned. In
// this case the value will be negative.
//
//
int string2Number( char *strInstring, int *intValue )
{
int intIndex1;
int intCharValue;
for ( intIndex1 = 0, *intValue = 0;
intIndex1 < strlen( strInstring );
intIndex1++ )
{ intCharValue = char2Number(strInstring[intIndex1]);
if ( intCharValue < 0 ) return 0;
*intValue = *intValue * 10 + intCharValue;
if ( *intValue < 0 ) return 0; }
return -1;
}

// ***** Main ************************************************************

int main( int intArgCount,
char *strArgValues[] )
{
if ( intArgCount == 2 && strcmp( strArgValues[1], "/?" ) == 0 )
{
printf( strcat(strcat("The %s program calculates primes ",
"in a user-specifiable range. "),
"Use the following syntax: %s"),
strArgValues[0],
SYNTAX_REMINDER );
return 0;
}
int intStart;
int intFinish;
if ( intArgCount < 3
||
! string2Number(strArgValues[1], &intStart)
||
! string2Number(strArgValues[2], &intFinish) )
{
printf( "Syntax: %s\n", SYNTAX_REMINDER );
return -1;
}
int intSieveLimit = SIEVESIZE;
if ( intArgCount > 3
&&
( ! string2Number(strArgValues[3], &intSieveLimit)
||
intSieveLimit > SIEVESIZE ) )
{
printf( "Sieve limit is not valid\n" ); return 0;
}
printf( strcat(strcat("Sieve of Eratosthenes primes from least prime >= %d ",
"to greatest prime <= %d\n"),
"Sieve contains %d entries\n"),
MAX(intStart, 3),
intFinish,
intSieveLimit );
int intSieve[SIEVESIZE];
int intPrimes = 0;
int intSievePrimes = 0;
int intDisplayedPrimes = 0;
int intTest;
int intHalfway;
int intIndex1;
int intFound;
time_t ttTimeStart; time( &ttTimeStart );
int intFoundInSieve = 0;
int intFoundUsingBruteForce = 0;
for ( intTest = 3; intTest <= intFinish; intTest = intTest + 2 )
{
intHalfway = (int)(intTest / 2);
intFound = 0;
for ( intIndex1 = 0;
intIndex1 < intSievePrimes
&&
intSieve[intIndex1] <= intHalfway;
intIndex1++ )
if ( IS_FACTOR( intTest, intSieve[intIndex1] ) )
{ intFound = 1; break; }
if ( ! intFound )
for ( intIndex1 =
intSievePrimes > 0 ? intSieve[intSievePrimes - 1] + 2 : 3;
intIndex1 <= intHalfway;
intIndex1 = intIndex1 + 2 )
if ( IS_FACTOR( intTest, intIndex1 ) )
{ intFound = 2; break; }
switch ( intFound )
{
case (0):
{
if ( intSievePrimes < intSieveLimit )
{
intSieve[intSievePrimes] = intTest;
intSievePrimes++;
}
intPrimes++;
if (intTest >= intStart)
{
intDisplayedPrimes++;
printf( "%d%s\n",
intTest,
intPrimes == intSieveLimit ?
" End of the sieve" : "" );
}
break;
}
case (1):
{
intFoundInSieve++; break;
}
case (2):
{
intFoundUsingBruteForce++; break;
}
default:
{
printf( "Programming error: unexpected case\n" );
return 0;
}
}
}
time_t ttTimeEnd; time( &ttTimeEnd );
int intIndex2;
for ( intIndex1 = 0; intIndex1 < intSievePrimes; intIndex1++ )
{
for ( intIndex2 = intIndex1 - 1;
intIndex2 >= 0;
intIndex2-- )
if ( IS_FACTOR(intSieve[intIndex1], intSieve[intIndex2]) )
{
printf( strcat( "Programming error: nonprimes occur in the ",
"sieve at %d and %d: %d and %d\n" ),
intIndex1, intIndex2,
intSieve[intIndex1], intSieve[intIndex2] );
break;
}
if ( intIndex2 >= 0 ) break;
}
if ( intIndex1 != intSievePrimes )
{
return 0;
}
printf( "Number of primes found: %d\n", intPrimes );
printf( "Number of nonprimes found using the sieve: %d\n", intFoundInSieve );
printf( "Number of nonprimes found using brute force: %d\n", intFoundUsingBruteForce );
printf( "Number of primes in the sieve: %d\n", intSievePrimes );
printf( "Number of primes displayed: %d\n", intDisplayedPrimes );
printf( "Time in approximate seconds: %d\n",
(long)ttTimeEnd - (long)ttTimeStart );
return 0;
}

2007-02-26 17:30:54 · answer #1 · answered by Ron H 6 · 0 0

//I haven't tested this function yet, but I think it should work for you

bool IsPrime(int nNum)
{
int i;

if(nNum==1)
{
return true;
}

for(i=2;i {
if((nNum/i)*i==nNum)
{
return true;
}
}

return false;
}

2007-02-27 01:26:35 · answer #2 · answered by Anonymous · 0 0

fedest.com, questions and answers