Smallest prime greater than a given value

[jay sturges]

   I have found that when dealing with whole number results 
   it is a far better to create trivial routines to approximate
   at a lower level of accuracy.  By doing so one can experience
   multitudes of performance increase as well as still achieving
   the same level of accuracy.
  
   The following source code contains a power series for a
   square root function.  I have found that using this function
   you can actually increase performance if accuracy to a real
   value is not required.  As below with calculating a prime
   number only 3 iterations of the power series is required.
   the reflected increase in performance was measured at 4X
   over standard C library sqrt( ).  This was measured on a
   Sun386i system with 80387 coproc
  
   Enjoy the tid-bit
   -Jay  				sun!sacto!pldote!jsturges
  
   
+--+--+--+--+--+  C U T +--+--+--+--+--+
#include <stdio.h>
/*
 * Prime( )
 *
 * simple routine to generate the smallest prime number
 * larger than a given number.  makes use of a very trivial
 * C implementation of a power series square root function.
 * the need for this function is to eliminate the need for 
 * the standard math library.  accuracy is not a issue as 
 * the end result is a whole number.
 *
 * Author:  Jay Sturges		sun!sacto!pldote!jsturges
 * Date  :  June 23, 1989
 *
 * Copyright:  NONE .... Just enjoy
 */

main( argc, argv )
int argc;
char **argv;
{
    argv++; argc--;
    while ( argc-- > 0) {
	printf("Smallest Prime larger --> %d\n",calc_prime(atoi(*argv++)));
    }
}

/*
 * calc_prime( )
 *      calculate the smallest prime larger than a given value
 */
int calc_prime( n )
int n;   			/* whole number as start */
{
int x;
int prime;
    
    x = n + 1;
    prime = 0;
    
    while ( prime <= n ) {
        if ( pchk( x ) && ( x > n ) ) {
            prime = x;			/* is prime */
        }
        else {
            x++;			/* try again */
        }
    }
    
    return( prime );
}

/*
 *  pchk( )
 *    checks if value is prime
 */
int pchk( n )
int n;
{
int max;
int i;
    
    max = trivial_sqrt( n ) + 1;
    
    for (i = 2; i < max; i++) {
        if ( !(n % i) ) {
            return( 0 );
        }
    }
    
    return( 1 );	/* prime */
}

#define M	3		/* minimum iterations for whole numbers */

/*
 * trivial_sqrt( )
 *     return the integer sqrt of the value
 */
int trivial_sqrt( n )
int n;
{
int i;
float x;
float y;
float a;

        y = ( float ) n;
        x = y;


        /*
         * square root 
	 *
	 *                 2
	 *  X    =  X  -  X  -  A
         *   i+1     i     i
         *               ---------
         *                  2X
         *                    i
	 * Where:
	 *        A  = n
	 *        X  = n
	 *         1
	 */
	for ( i = 0; i < M; i++ )
	    x = x - ( ( ( x*x ) - y ) / ( 2 * x ) );

	return( (int) x );
}