/* This program counts the primes below 1,000,000.
 *
 * (c) Richard Heathfield 1994.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define BIT_IS_SET(s,b) ((s[(b) >> 3]) &  (1 << ((b) & 7)))
#define SET_BIT(s,b)  ((s[(b) >> 3]) |= (1 << ((b) & 7)))
#define HIGHROOT 1000L
#define HIGHROOTO2 500L
#define HIGHNUM 1000000L
#define HIGHNUMO2 500000L
#define MEMSIZE 62500U
#define INITPRIMES 500001L
int main(void)
{
    unsigned char BitMap[62500] = {0};
    unsigned long NumPrimes = INITPRIMES, Low, Candidate, Start, End;

    Start = clock();
    for(Low = 3L; Low < HIGHROOT; Low += 2)
    {
        if(!BIT_IS_SET(BitMap, Low >> 1))
        {
            for(Candidate = (Low * 3) >> 1;
                Candidate < HIGHNUMO2;
                Candidate += Low)
            {
                if(!BIT_IS_SET(BitMap, Candidate))
                {
                    NumPrimes--;
                    SET_BIT(BitMap, Candidate);
                }
            }
        }
    }
    End = clock();
    printf("\n\nNumber of primes=%ld,time=%.3f s.\n", NumPrimes, (double)(End - Start) / CLOCKS_PER_SEC);
    return 0;
}