#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 ;
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 ) ) ;
return 0;
}
/*
Input: 3 6 20
Output:2 5, 5 7,19 23
*/
No comments:
Post a Comment