/*
  Author:  Pate Williams (c) 1997

  "Exercise 1.1. Primes in intervals.
  Write a computer program for the following:
  read two (odd) integers m and n >= m. Generate
  and array containing the odd primes below
  sqrt(n). Sieve out all composites between
  m and n by the sieve of Eratosthenes, utilizing
  the primes below sqrt(n). Print the primes
  between m and n and their numbers. Suitable
  test values are: (m, n) = (99, 201),
  (12113, 12553), (9553, 9585)." -Hans Riesel-
  See "Prime Numbers and Computer Methods for
  Factorization" by Hans Riesel second edition
  page 7.
*/

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

#define BITS_PER_LONG   32
#define BITS_PER_LONG_1 31
#define SIZE 8192

long get_bit(long i, long *sieve)
{
  long b = i % BITS_PER_LONG;
  long c = i / BITS_PER_LONG;

  return (sieve[c] >> (BITS_PER_LONG_1 - b)) & 1;
}

void set_bit(long i, long v, long *sieve)
{
  long b = i % BITS_PER_LONG;
  long c = i / BITS_PER_LONG;
  long mask = 1 << (BITS_PER_LONG_1 - b);

  if (v == 1)
    sieve[c] |= mask;
  else
    sieve[c] &= ~mask;
}

void Sieve(long n, long *sieve)
{
  long c, i, inc;

  set_bit(0, 0, sieve);
  set_bit(1, 0, sieve);
  set_bit(2, 1, sieve);
  for (i = 3; i <= n; i++)
    set_bit(i, i & 1, sieve);
  c = 3;
  do {
    i = c * c, inc = c + c;
    while (i <= n) {
      set_bit(i, 0, sieve);
      i += inc;
    }
    c += 2;
    while (!get_bit(c, sieve)) c++;
  } while (c * c <= n);
}

void Sieve_Interval(long m, long n, long *sieve)
{
  long a, base[SIZE], c, i, inc, s = sqrt(n);

  Sieve(s, base);
  for (i = m; i <= n; i++)
    set_bit(i - m, i & 1, sieve);
  c = 3;
  do {
    a = m / c;
    if (m % c == 0) i = a * c;
    else i = a * c + c;
    if (i == c) i += c;
    inc = c;
    while (i <= n) {
      set_bit(i - m, 0, sieve);
      i += inc;
    }
    c += 2;
    while (!get_bit(c, base)) c++;
  } while (c * c <= n);
}

int main(void)
{
  long count = 0, i, m, n;
  long sieve[SIZE];

  printf("m = ");
  scanf("%ld", &m);
  printf("n = ");
  scanf("%ld", &n);
  Sieve_Interval(m, n, sieve);
  for (i = 0; i < n - m + 1; i++) {
    if (get_bit(i, sieve)) {
      printf("%5ld ", i + m);
      count++;
      if (count % 5 == 0) printf("\n");
    }
  }
  if (count % 5 != 0) printf("\n");
  printf("number of primes = %ld\n", count);
  return 0;
}