gistfile1.cpp

#include <stdlib.h>
#include <stdio.h>
#include <mem.h>
#include <conio.h>
#include <bios.h>

inline int GetField(const long num);
inline void SetField(const long num);

const long MaxNum=500000L;
int * BitField;
int main()
{
	register long prime=3;
	register long p=0;
	int display;
	printf("Display? ");
	display = getche();
	printf("\n");
	if ((char)display=='Y' || (char)display=='y')
		display=1;
	else {
		display=0;
		printf("\nWorking...\n");
	}

	long timer=biostime(0, 0);

	BitField=new int[(unsigned)(MaxNum>>4)+1];
	setmem(BitField, (unsigned int)(MaxNum>>3), 0);
	while (prime<(MaxNum>>1)) {
		if (GetField(prime)==0) {
			if (display) printf("%8lu", prime);
			p=prime;
			do {
				p+=prime;
				if (p&1) {
					SetField(p);
				}
			} while (p<=MaxNum-prime);
		}
		prime+=2;
	}
	if (display) {
		for (p=prime; p<=MaxNum; p+=2) {
			if (GetField(p)==0) {
				printf("%8lu", p);
			}
		}
	}
	timer=biostime(0, 0)-timer;
	printf("\n\n Time taken for prime numbers < 500 000 = %f seconds"
		, (double)timer*3600.0/65536.0);
	return 0;
}


inline int GetField(const long num) {
	long n=(num-3)>>1;
	return (BitField[unsigned(n>>4)] >> (unsigned(n)&15))&1;
}

inline void SetField(const long num) {
	long n=(num-3)>>1;
	BitField[unsigned(n>>4)] |= 1<<(unsigned(n)&15);
}