Friday, January 13, 2012

Calculate Next & Previous prime of a number

#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