Prime Numbers

[Joshcannon]

This Program I have needs to make the prime numbers and label them as 'P'. This is what I was given. There's suppose to be 1 line of code that will fix it.

  void  identifyPrimes ( char number[], int ARRAY_SIZE )
  {
  int  leastU  =  indexOfLeastU ( number, ARRAY_SIZE ) ;

  while ( leastU >= 0 )
    {
    number [leastU]  =  'P' ; // 'P' for Prime

    // mark multiples as Composite ...
    for ( int i = (2 * leastU) ; i < ARRAY_SIZE  ; i += leastU )
      number [leastU]  =  'C' ; // 'C' for Composite

    leastU  =  indexOfLeastU ( number, ARRAY_SIZE ) ;
    } // end while loop
  } // end identifyPrimes function 

[Albatross]

What would you like us to do?

-Albatross

[Joshcannon]

Well I see that its makeing all the numbers as 'P', i need just the prime numbers as 'P'

[Computergeek01]

A non-static, non-Macro variable labeled in all caps AND an array of numerical values that have to be mathematically evaluated represented as chars ... *Head->Desk Head->Desk Head->Desk*.

What does the oh so terribly named "indexOfLeastU()" function do? Bonus points if you just copy and paste the code for that function.

[Joshcannon]

This is the whole program. It's suppose to just print the prime numbers. I can't figure out whats wrong though.

/*  --------------------------------------------------------
    HW_10_Solution.cpp    J. Solheim    15 NOV 2013
    This program uses a "char" array & the method known as
    “the Sieve of Erastosthenes” to determine & print all
    prime numbers up to 1000.
    -------------------------------------------------------- */

#include <cstdlib>
#include <iostream>
using namespace std ;

/*  --------------------------------------------------------
    Function initializeNumbers sets numbers 0 & 1 to Ignore,
    and sets numbers 2 & above to Unvisited.
    -------------------------------------------------------- */
void initializeNumbers ( char number[], int ARRAY_SIZE )
  {
  number[0]  =  'I' ; // 'I' means Ignore
  number[1]  =  'I' ;

  for ( int i = 2 ; i < ARRAY_SIZE ; i ++ )
    number[i]  =  'U' ; // 'U' means Unvisited
  } // end initializeNumbers function

/*  --------------------------------------------------------
    Function indexOfLeastU returns the least index such that
    the character stored at that index is 'U', with the
    exception that -1 is returned if no array element has
    value 'U'.
    -------------------------------------------------------- */
int indexOfLeastU ( char number[], int ARRAY_SIZE )
  {
  for ( int i = 0 ; i < ARRAY_SIZE ; i ++ )
    if ( number[i] == 'U' )
      return  i ;

  return  -1 ;
  } // end indexOfLeastU function

/*  --------------------------------------------------------
    Function identifyPrimes identifies which numbers are
    prime by placing 'P's at those indices.
    Composite #'s are marked with 'C's.
    -------------------------------------------------------- */
void  identifyPrimes ( char number[], int ARRAY_SIZE )
  {
  int  leastU  =  indexOfLeastU ( number, ARRAY_SIZE ) ;

  while ( leastU >= 0 )
    {
    number [leastU]  =  'P' ; // 'P' for Prime

    // mark multiples as Composite ...
    for ( int i = (2 * leastU) ; i < ARRAY_SIZE  ; i += leastU )
      number [leastU]  =  'C' ; // 'C' for Composite

    leastU  =  indexOfLeastU ( number, ARRAY_SIZE ) ;
    } // end while loop
  } // end identifyPrimes function

/*  --------------------------------------------------------
    Function printPrimes prints those array indices whose
    corresponding elements have the value 'P'.
    -------------------------------------------------------- */
void printPrimes ( char number[], int ARRAY_SIZE )
  {
  // print the indices at which a 'P' is stored ...
  cout << "\nThe prime numbers up to 1000 are:\n\n" ;
  for ( int i = 0 ; i < ARRAY_SIZE ; i ++ )
    if ( number[i] == 'P' )
      cout << i << '\t' ;
  cout << endl << endl ;
  } // end printPrimes function

int main ( )
  {
  // declare & initialize constants ...
  const int  MAX_NUMBER  =  1000 ;
  const int  ARRAY_SIZE  =  MAX_NUMBER + 1 ;

  // declare array ...
  char  number [ ARRAY_SIZE ]  =  { '\0' } ;

  initializeNumbers ( number, ARRAY_SIZE ) ;

  identifyPrimes ( number, ARRAY_SIZE ) ;

  printPrimes ( number, ARRAY_SIZE ) ;
  } // end main function

[Computergeek01]

Your function "indexOfLeastU()" is completely broken, back it up then delete it and start over. I think I can actually tell at what point you walked away from this code and came back to it since you seem to be trying to implement two different ideas.

[Joshcannon]

I'm completely lost right now.

[Joshcannon]

just focus on the identifyPrimes function right now. How can I make it so the prime numbers get declared as 'P'. That's all I need right now.

[Computergeek01]

Your "identifyPrimes" function passes it's variables to the "indexOfLeastU()" function which incorrectly tries to evaluate the index points in the array but in reality it only starts at 0 every time it is called and runs through the array until it sees the index 2 as 'U' where it then returns that number. So in reality your "indexOfLeastU()" function looks like it is what is supposed to be evaluating the individual numbers but since it's broken nothing you do to the "identifyPrimes()" function will fix this. Kudos on your notation by the way, that is an excellent habit to get into early on.

[snowright]

The use of char array and these ignored, unvisited flags etc. is more than unnecessary. You can surely find more than two stages for different numbers but with the information of in what position we are currently at the loop the sieve can easily be implemented with just to flags. Have a look at my following implementation. I did write it so you cannot copy&paste it straight to your own code; it is just something working you can take advantage of when writing your own version.

static const int CHECK_AMOUNT = 100; //Number of the first natural numbers whose primality we check ( including zero )

//Array that will eventually have C[ i ] = 1 for each composite and C[ i ] = 0 for each prime
//You could use a boolean array for better semantics
//Notice all rest of the elements are set to zero
int C[ CHECK_AMOUNT ] = { 1, 1, 0 };

int 	maxMultiplier, 
	prime = 2, 
	
	//We do not need to check divisibility for larger primes than the square root of the number we are observing
	maxPrime = floor( sqrt( CHECK_AMOUNT - 1 ) );

while( true )
{
	//Here we loop through primes and inside below determine which is the last multiple of the prime that still belongs to our range after which assign all the current prime multiplies to composite in our array
	//Notice we start from the power of two of the number, since all smaller multiplies definitely have a smaller prime divisor and like that are flagged as composite already
	maxMultiplier =  ( CHECK_AMOUNT - 1 ) / prime;
	for( int mul = prime; mul <= maxMultiplier; mul++ )
		C[ mul * prime ] = 1;


	//Loop until we find next prime or reach the last prime we need to check
	//If we wrote checking separately for the first prime 2 then we could here optimize and use C[ prime += 2 ] since clearly having an odd prime the next prime cannot be even so checking odd numbers would satisfy
	while( C[ ++prime ] && prime != maxPrime ) { }
	if( prime == maxPrime )
		break;
}