Coherent4.2.10/coh.386/nlp.c

/* $Header: /ker/coh.386/RCS/nlp.c,v 1.3 93/08/19 03:25:00 nigel Exp $ */
/*
 * Find next lower prime from a number
 * Only use for this module now is calculating NHASH given NBUF.
 *
 * Compile -DTEST=1 for test version.
 * $Log:	nlp.c,v $
 * Revision 1.3  93/08/19  03:25:00  nigel
 * Nigel's R83 (Stylistic cleanup)
 * 
 */

#include <common/_tricks.h>
#include <common/ccompat.h>
#include <common/xdebug.h>

#if	TEST

# include <stdio.h>
# define	TESTPRINT(args)		(printf args)
int		main		__PROTO((void));

#else

#define TESTPRINT(args)

#endif	/* ! TEST */

unsigned int		nlp		__PROTO ((unsigned int num));

__LOCAL__ int		isprime		__PROTO ((unsigned int num));
__LOCAL__ unsigned int	isqrt		__PROTO ((unsigned int num));


/************************************************************************
 * nlp
 *
 * Return the next prime strictly less than the given argument.
 * Return 0 if the argument is 0, 1, or 2.
 ***********************************************************************/
#if __USE_PROTO__
unsigned int nlp (unsigned int num)
#else
unsigned int
nlp (num)
unsigned int num;
#endif
{
	unsigned int ret;

	switch(num) {
	case 0:
	case 1:
	case 2:
		ret = 0;
		break;

	default:
		for (num--;  num > 2; num--) {
			if (isprime(num))
				break;
		}
		ret = num;
	}

	return ret;
}

/************************************************************************
 * isprime
 *
 * Return nonzero if the argument is prime, else return 0.
 * Return 0 if the argument is 0 or 1.
 ***********************************************************************/
#if __USE_PROTO__
__LOCAL__ int isprime (unsigned int num)
#else
__LOCAL__ int
isprime (num)
unsigned int num;
#endif
{
	int ret = 1;
	unsigned int nsqrt = isqrt(num);
	unsigned int f;

	switch(num) {
	case 0:
	case 1:
		ret = 0;
		break;
	default:
		if ((num & 1) == 0)
			ret = 0;
		else for (f = 3;  f <= nsqrt;  f++) {
			if ((num % f) == 0) {
				ret = 0;
				break;
			}
		}
	}

	TESTPRINT(("isprime(%u) = %d\n", num, ret));

	return ret;
}

/************************************************************************
 * isqrt
 *
 * Return the smallet integer greater than or equal to the square root
 * of the argument.
 ***********************************************************************/
#if __USE_PROTO__
__LOCAL__ unsigned int isqrt (unsigned int num)
#else
__LOCAL__ unsigned int
isqrt (num)
unsigned int num;
#endif
{
	unsigned int ret;
	int guess;
	int guess2;
	int loopct;

	switch(num) {
	case 0:
	case 1:
		loopct = 0;
		ret = num;
		break;
	default:
		/* Newton's method, adapted for integers. */
		guess = num >> 1;

		/* Use binary to get quick first guess. */
		guess = 1 << (__MOST_BIT_UINT(num) / 2);

		for (loopct = 0;  loopct < 32;  loopct++) {
			guess2 = num / guess;

			TESTPRINT(("g1 = %u  g2 = %u\n", guess, guess2));

			if (guess >= guess2) {
				ret = guess;
				if (guess - guess2 <= 1) {
					break;
				}
			} else {
				ret = guess2;
				if (guess2 - guess <= 1) {
					break;
				}
			}
			guess = (guess2 + guess) / 2;
		}
		if (ret * ret < num)
			ret++;
	}

	TESTPRINT(("isqrt(%d) = %d  loopct = %d\n", num, ret, loopct));

	return ret;
}

#if TEST

#if __USE_PROTO__
int main (void)
#else
int main ()
#endif
{
	unsigned int num;

	for (;;) {
		printf("enter a number: ");
		if (scanf("%u", &num))
			printf("Next lower prime from %u is %u\n",
			  num, nlp(num));
		else
			break;
	}

	return 0;
}

#endif /* TEST */