/* ----------------------------------------------------------------------- *
 * PrimePrint: Prints all the primes below the number entered by the user
 *             using bit operations and the sieve of Eratosthenes
 *
 * Author: Suzi Anvin
 *
 * Purpose: Practice using bit operators in C
 * ----------------------------------------------------------------------- */

#include <stdint.h>
#include <stdio.h>
#include <math.h>

inline void clr_bit (uint8_t array[], unsigned int bit)
{
  array[bit/8] &= ~(1<<(bit%8));
}

inline int test_bit (const uint8_t array[], unsigned int bit)
{
  return (array[bit/8]>>(bit%8)) & 1;
}

void primeprint (int bits)
{
  uint8_t array[(bits+7)/8];	/* array to tally primes.  Length set
                                 *  dynamically to the # of bytes needed to 
                                 * capture the user's maximum value */
  int i, j;			/* counters */
  int max_bytes = (bits+7)/8;	/* # of bytes needed in array */
  int max_root = sqrt(bits);	/* square root of the user's maximum */
  int first = 0;		/* T/F - have we printed a number yet? */
  int chars = 0;		/* # of characters printed on current line */

  for (i=0; i < max_bytes; i++) { /* Initializing all bits in array to 1 */
    array[i] = ~0;
  }
  /* clearing the non-prime numbered bits in the array */
  clr_bit (array, 0);
  clr_bit (array, 1);

  for (i=0; i <= max_root; i++) {
    if (test_bit (array, i) == 1) {
      for (j = 2 * i; j < bits; j += i) {
	clr_bit (array, j);
      }
    }
  }

  /* printing out only the prime numbers (i.e. all remaining set bits) */
  chars = printf("The following numbers are prime:");
  for (i=0; i < bits; i++) {
    if (test_bit (array, i) == 1) {
      if (first) {
	putchar(',');
	chars++;
	if (chars >= 70) {
	  putchar('\n');
	  chars = 0;
	}
      }
      chars += printf(" %d", i);
      first = 1;
    }
  }
  putchar('\n');
}

int main ()
{
  char line[50];
  int max;			/* maximum value of primes to print */

  /* Inputing maximum value from user, then turning that value over to
   * a separate function to print the primes.  This is needed to allow
   * the tally array to be sized based on the maximum set by the user. */

  printf("Please give the maximum value for the primes to find: ");
  fgets(line, sizeof(line), stdin);
  sscanf(line, "%d", &max);
  primeprint (max + 1);		/* need extra bit for the zero in array */
  return (0);
}