/* --------------------------------------------------------------------- 
**  Figure 11.12  Calculating prime numbers.
**  Figure 11.13  Functions for the prime number program.
** --------------------------------------------------------------------- 
*/
#include "tools.h" 

#define MANY 3000
void print_table( int primes[], int num_primes );
bool divisible( int candidate, int primes[], int n ); /* Is it nonprime? */

void main( void )                                                      
{
    int k;                      /* Integer being tested. */
    int primes[MANY] = {2};     /* Start with the only even prime in table. */       
    int n = 1;                  /* Number of primes in table. */

    banner();
    /* Fill table with the first MANY prime numbers ---------------------- */
    for (k = 3; n <= MANY; k += 2)  {       /* Test the next odd integer. */
                                            /* Quit when table is full. */
        if (!divisible( k, primes, n )) {   /* If it is a prime... */
            primes[n] = k;                  /* ... put it in the table... */            
            ++n;                            /* ... and count it. */             
        }
    }   
    print_table( primes, MANY );            /* Print table of primes. */
    bye();
}

/* --------------------------------------------------------------------- 
// Print the list of prime numbers one per line.
*/
void 
print_table( int primes[], int num_primes )
{
    int m;                  /* Loop index for primes table */
    printf( "\n The First %i Primes\n ---------------------\n", num_primes );
    for (m = 0; m < num_primes; m++) printf( "%10i\n", primes[m] );
    printf( " ---------------------\n" );                                                      
}

/* -----------------------------------------------------------------   
// Test candidate number for divisibility by primes in the table.     
// Return true if proper divisor is found, false otherwise.   
*/
bool 
divisible( int candidate, int primes[], int n )
{    
    int m;                  /* Loop counter */
    int last = (int) sqrt( candidate );
    bool found = false;     /* Later set to true if divisor is discovered. */

    /* Divide by every prime < square root of candidate. */
    for (m = 0; m < n && primes[m] <= last; ++m) {          
        if (candidate % primes[m] == 0) {
            found = true;
            break;
        }
    }
    return found;   
}