//=========================================================================
#define PROGRAMMER "BAHN, William"
#define PROG_CODE  "bahw"
#define COURSE     "ECE-1021"
#define YEAR       (2003)
#define TERM       "Fall"
#define SECTION    (0)
#define ASSIGNMENT "RWA 4.2"
#define REVISION   (0)
#define TITLE      "Real World Application from Section 4.2"
#define SUBTITLE   "Generating Prime Numbers"
#define EMAIL      "wbahn@eas.uccs.edu"
#define FILENAME   "rwa0402.c"
//=========================================================================

// PROBLEM:
//
// MODIFIED FROM TEXT
//
// Print all positive prime numbers less than or equal to n.
//
// PSEUDOCODE
// 1) REM: Print Header
// 2) GET: n from UserREM: Get Global Data
// 3) SET: i = 2
// 3) LOOP: while i <= n
// 3.1) IF: i is prime
// 3.1.1) PUT: i to screen
// 4) PUT: Program Termination Message to screen.
// 5) EXIT program

//== DETERMINING IF i IS PRIME ============================================
// If i is NOT prime, then there exists at least one value k such that
//    1 < k < i  AND  i % k = 0
//
// Therefore a brute force way to determine if i is prime is as follows:
//
// 1) SET: k = 2
// 2) SET: prime = TRUE
// 2) LOOP: while k < i
// 2.1) IF: (0 == i % k)
// 2.1.1) SET: prime = FALSE
// 2.2) SET: k = k+1
//
// That above can be greatly improved by noting that:
//
//    If i is even (and greater than 2) then it is not prime,
//       Therefore:
//          start i at 3 and increment by 2
//          start k at 3 and increment by 2
//
//    The largest possible divisor of i is sqrt(i)
//       Therefore:
//          stop k once it reaches sqrt(i)
//
//    The is no point in checking further once a divisor is found.
//       Therefore:
//          include the prime flag in the while condition
//
//    The only divisors that need be checked are prime numbers.
//       Therefore:
//          keep a list of primes thus far and only check those.
//       However:
//          this is beyond the scope of what has been covered thus far.
//
// The improved pseudocode for determining if i is prime is:
//
// 1) SET: k = 3
// 2) SET: kmax = sqrt(i)
// 3) SET: prime = TRUE
// 4) LOOP: while (prime) AND (k < kmax)
// 4.1) IF: (0 == i % k)
// 4.1.1) SET: prime = FALSE
// 4.2) SET: k = k+2
//
// Note that the above will work correctly for i = 2 and i = 3

//== INCLUDE FILES ========================================================
#include <stdio.h> // printf(), scanf(), EOF
#include <math.h>  // sqrt()
#include <conio.h>  // gotoxy()
//== FUNCTION PROTOTYPES ==================================================
void PrintHeader(void);

//== MAIN FUNCTION ========================================================
int main(void)
{
	long int i, n, j, kmax;
	int k;
	int prime;

	PrintHeader();
	printf("\n"); // Print a blank line

	// ********** GET THE VALUE OF N FROM USER **********

	printf("Enter the largest integer to check: ");
	scanf("%li", &n);

	j=0;
	// Treat 2 as a special case (only even prime)
	if(1 < n)
		printf("Prime #%2li: %5i\n", ++j, 2);
	else
		printf("No primes less than or equal to %li\n", n);

	for(i = 3; i <= n; i+=2)
	{
		k = 3;
		kmax = floorl(sqrtl((long double) i));
		prime = 1;
		while( (prime) && (k <= kmax) )
		{
			if( !(i % k) )
				prime = 0;
			k +=2;
		}
		if(prime)
			printf("Prime #%2li: %5i\n", ++j, i);
	}
	printf("# of Primes less than or equal to %li: %li\n", n, j);
	printf("PROGRAM TERMINATED");
	return(0);
}

//== SUPPORT FUNCTIONS ====================================================
void PrintHeader(void)
{
	printf("========================================"
			 "=======================================\n");
	printf("Course....... %s-%i (%s %i)\n", COURSE, SECTION, TERM, YEAR);
	printf("Programmer... %s (%s)\n", PROGRAMMER, PROG_CODE);
	printf("Assignment... %s (Rev %i) (Source Code in %s)\n",
		ASSIGNMENT, REVISION, FILENAME);
	printf("Description.. %s\n", TITLE);
	printf("              %s\n", SUBTITLE);
	printf("========================================"
			 "=======================================\n");

	return;
}