# PRIME1 : WHY RUNTIME EXCEPTION ?

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

unsigned short int *primes;
unsigned short int size;

char is_prime(unsigned int n)
{
unsigned short i, lim, num;

``````if(n == 1)
return 0;
else if(n <= 3)
return n;
else
{
unsigned short i = 0, lim = sqrt(n), num = primes[i];

while(num && (num <= lim))
{

if(n % num == 0)
{
return 0;
}
i++;
num = primes[i];
}
return 1;
}
``````

}

void populate_primes(unsigned short n)
{
unsigned short num = 7, i = 1, j;
char inc = 2;

``````primes = (unsigned short *)malloc(sizeof(unsigned short)*n/3);

for(j = 0; j < n/3; j++)
primes[j] = 0;

primes[0] = 5;

while(num <= n)
{
if(is_prime(num))
{
primes[i] = num;
i++;
}
inc = (inc*-1)+6;
num += inc;
}
``````

}

void free_primes()
{
free(primes);
primes = NULL;
}

void print_prime_nos(unsigned int m, unsigned int n)
{
unsigned int num = m;
char inc = 5;

``````populate_primes(sqrt(n));

while((num <= n) && (num <= 3))
{
if(is_prime(num))
printf("%u\n", num);
num++;
}

if(num <= n)
{
if(num%6 <= 1)
{
num = (num/6*6)+1;
inc = 2;
}
else
{
num = (num/6*6)+5;
inc = 4;
}
}

while(num <= n)
{
if(is_prime(num))
printf("%u\n", num);
inc = (-1*inc)+6;
num += inc;
}

free_primes();
``````

}

int main()
{
unsigned short t;
scanf("%u", &t);

``````while(t-- > 0)
{
unsigned int m, n;
scanf("%u", &m);
scanf("%u", &n);

print_prime_nos( m, n);

printf("\n");
}

return 0;
``````

}

//