Search This Blog

Loading...

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
*/

No comments:

Post a Comment