tested my code on a windows machine powered by intel 720QM, I've only timed preprocessing, since writing (to console) it self takes large amount of time.
110s 9-10s 6-7s & 611MB 61MB ram
#define isprime(X) ((X)&1?(!(bank[(X)>>6]&(1<<(((X)&63)>>1)))):(X)==2)
#define sqr(X) ((X)*(X))
#define maxpossible (1000000000L)
unsigned int bank[maxpossible/64];
int beg = time(0);
unsigned long i,k,a,b;
unsigned long d,x,maxpossible_2 = maxpossible>>1;
unsigned long maxpossiblesqrt = sqrt((double)maxpossible)+1;
bank ^= 1;
d = (((i<<5)|k)<<1)+1;
printf("preprocessing needed %d seconds\n" ,time(0) - beg);
printf("enter two positive number lower than %d\n" ,maxpossible );
scanf("%d %d" ,&a ,&b);
my code now compiles both in C++ and C (i've used c++ compiler myself), also fixed a small bug!
to save if a number is prime or not you only need 1 bit, so you can easily reduce size of data needed to store if a number is prime by 8 if you use all 8 bits in each byte.
and besides the only even number which is prime is 2, so I can omit all the even numbers and only save if odd numbers are prime.
it first checks if a number is odd by computing
((X)&1), if a number is odd the result is 1 otherwise it's zero (note that odd numbers have 1 in their last bit).
in case of even number I can easily check if
(X)==2 and it's the same as checking if an even number is prime
in case of odd number I have to look into my table, first I need to find out which cell contains data for (X), and then which bit is telling if my number is prime. as I explained each cell contains 8 bits so 8 numbers and even numbers are completely off my list. so
(X) without it's 4 first bits generates cell number.
then to find out bit location I use (1<<(((X)&14)>>1)) which means : only keep bit 2,3 and 4 of my number, shift right 1 place and put data in bits 1,2 and 3 respectively. so far
(((X)&14)>>1) it generates bit number the next step is to create a mask that checks only for that specific bit
(1<<(((X)&14)>>1)) it means shift a number with single first bit as true
(((X)&14)>>1) places to left. in the end it's only checking if that specific mask applied to chosen data cell is true or false, which is done by only applying the mask by bitwise & operator (c++ itself checks if result is none-zero)
if you got how isprime works the rest is easy, it's using Sieve of Eratosthenes method to eliminate all none-prime numbers. the only thing I can mention is if p is a prime number, it starts from p^2 with step of size 2*p and eliminates all none-prime numbers to increase performance.