Sieve of Erastosthenes

[Joshcannon]

This was a previous homework assignment, the assignment was you have to change 1 line and 1 line only to fix the program. Could anyone help me find that line, it's really getting to me that I never found it.

/*  --------------------------------------------------------
    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 

[Danny Toledo]

Take a really close look at line 55 and try and figure out what it is doing ;)

[Joshcannon]

Its marking all the number's as c?

[Danny Toledo]

Line 55 is supposed to be setting every number in the array that is divisible by the "current" prime number (number[leastU]) to 'C'. What it is actually doing is setting number[leastU] (which is prime) to 'C'. After the for loop (line 54) completes, a new prime number is selected (line 57)(which, because you only change number[leastU] to composite, is number[leastU + 1]. It keeps doing this until every element of number is a 'C' (which you don't want).

As stated, this is because you set number[leastU] to composite in the for loop. What you need to do is set number[i] to composite (i is the index that is used in the header of the for loop to visit each element divisible by number[leastU]).

Hope that helps.

[Joshcannon]

whenever I figure out things that are way easier then I'm making them i just want to break down and cry. You're my hero. Thank you.