# Calculate Next & Previous Prime of a Number - C Program

#include <stdio.h>
#include <conio.h>
#define SIZE_N 1060
#define SIZE_P 250

bool flag [SIZE_N] ;
long prime [SIZE_P] ;

void seive ()
{
long i, j, r, c = 0 ;

//flag[1] = true ;
//special case when 1 considered as prime
flag[2] = true ;

for (i = 3; i <= SIZE_N; i += 2)

flag[i] = true ;

for (i = 3; i <= SIZE_N; i +=2 )
{
if (flag[i] == true)
{
if (SIZE_N / i >= i)
{
r = i * 2 ;

for (j = i * i; j <= SIZE_N; j += r)
flag[j] = false ;
}
}
}
}

long next_prime ( long p ) // seive required
{
long i ;
if ( p == 0 || p == 1 ) return 2 ;

if ( !( p % 2 ) ) p += 1 ;
else p += 2 ;

for ( i = p; ; i += 2 )
if ( flag[i] ) return i ;
}

long previous_prime ( long p )
{
int i ;
if ( p < 3 ) return -1 ;

if ( !( p % 2 ) ) p -= 1 ;
else p -= 2 ;

for ( i = p; ; i -= 2 )
if ( flag[i] ) return i ;
}

int main ()
{
long n ;
clrscr();
seive () ;
while (scanf ( "%ld", &n ) == 1)
//when n = 3 Than previous prime = 2;Special case;
printf ( "pre = %ld next = %ld\n", previous_prime ( n ), next_prime ( n ) ) ;
getch();
}

/*
Input: 3 6 20
Output:2 5, 5 7,19 23
*/