![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to nlp.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / b / STREAMS / coh.386|
Return to nlp.c CVS log | Up to [MW Coherent from dump] / coherent / b / STREAMS / coh.386 |
1.1 root 1: /*
2: * File: nlp.c
3: *
4: * Purpose: find next lower prime from a number
5: * Only use for this module now is calculating NHASH given NBUF.
6: *
7: * Compile -DTEST=1 for test version.
8: *
9: * Revised: Wed Aug 4 12:44:29 1993 CDT
10: */
11:
12: /*
13: * ----------------------------------------------------------------------
14: * Includes.
15: */
16: #include <common/_tricks.h>
17: #include <common/ccompat.h>
18: #include <common/xdebug.h>
19:
20: /*
21: * ----------------------------------------------------------------------
22: * Definitions.
23: * Constants.
24: * Macros with argument lists.
25: * Typedefs.
26: * Enums.
27: */
28: #if TEST
29: #include <stdio.h>
30: #define TESTPRINT(args) (printf args)
31: int main __PROTO((void));
32: #else
33: #define TESTPRINT(args)
34: #endif
35:
36: /*
37: * ----------------------------------------------------------------------
38: * Functions.
39: * Import Functions.
40: * Export Functions.
41: * Local Functions.
42: */
43: unsigned int nlp __PROTO ((unsigned int num));
44:
45: __LOCAL__ int isprime __PROTO ((unsigned int num));
46: __LOCAL__ unsigned int isqrt __PROTO ((unsigned int num));
47:
48: /*
49: * ----------------------------------------------------------------------
50: * Global Data.
51: * Import Variables.
52: * Export Variables.
53: * Local Variables.
54: */
55:
56: /*
57: * ----------------------------------------------------------------------
58: * Code.
59: */
60:
61: /************************************************************************
62: * nlp
63: *
64: * Return the next prime strictly less than the given argument.
65: * Return 0 if the argument is 0, 1, or 2.
66: ***********************************************************************/
67: #if __USE_PROTO__
68: unsigned int nlp (unsigned int num)
69: #else
70: unsigned int
71: nlp (num)
72: unsigned int num;
73: #endif
74: {
75: unsigned int ret;
76:
77: switch(num) {
78: case 0:
79: case 1:
80: case 2:
81: ret = 0;
82: break;
83: default:
84: for (num--; num > 2; num--) {
85: if (isprime(num)) {
86: break;
87: }
88: }
89: ret = num;
90: }
91:
92: return ret;
93: }
94:
95: /************************************************************************
96: * isprime
97: *
98: * Return nonzero if the argument is prime, else return 0.
99: * Return 0 if the argument is 0 or 1.
100: ***********************************************************************/
101: #if __USE_PROTO__
102: __LOCAL__ int isprime (unsigned int num)
103: #else
104: __LOCAL__ int
105: isprime (num)
106: unsigned int num;
107: #endif
108: {
109: int ret = 1;
110: unsigned int nsqrt = isqrt(num);
111: unsigned int f;
112:
113: switch(num) {
114: case 0:
115: case 1:
116: ret = 0;
117: break;
118: default:
119: if ((num & 1) == 0)
120: ret = 0;
121: else for (f = 3; f <= nsqrt; f++) {
122: if ((num % f) == 0) {
123: ret = 0;
124: break;
125: }
126: }
127: }
128:
129: TESTPRINT(("isprime(%u) = %d\n", num, ret));
130:
131: return ret;
132: }
133:
134: /************************************************************************
135: * isqrt
136: *
137: * Return the smallet integer greater than or equal to the square root
138: * of the argument.
139: ***********************************************************************/
140: #if __USE_PROTO__
141: __LOCAL__ unsigned int isqrt (unsigned int num)
142: #else
143: __LOCAL__ unsigned int
144: isqrt (num)
145: unsigned int num;
146: #endif
147: {
148: unsigned int ret;
149: int guess;
150: int guess2;
151: int loopct;
152:
153: switch(num) {
154: case 0:
155: case 1:
156: loopct = 0;
157: ret = num;
158: break;
159: default:
160: /* Newton's method, adapted for integers. */
161: guess = num >> 1;
162:
163: /* Use binary to get quick first guess. */
164: guess = 1 << (__MOST_BIT_UINT(num) / 2);
165:
166: for (loopct = 0; loopct < 32; loopct++) {
167: guess2 = num / guess;
168:
169: TESTPRINT(("g1 = %u g2 = %u\n", guess, guess2));
170:
171: if (guess >= guess2) {
172: ret = guess;
173: if (guess - guess2 <= 1) {
174: break;
175: }
176: } else {
177: ret = guess2;
178: if (guess2 - guess <= 1) {
179: break;
180: }
181: }
182: guess = (guess2 + guess) / 2;
183: }
184: if (ret * ret < num)
185: ret++;
186: }
187:
188: TESTPRINT(("isqrt(%d) = %d loopct = %d\n", num, ret, loopct));
189:
190: return ret;
191: }
192:
193: #if TEST
194: #if __USE_PROTO
195: int main(void)
196: #else
197: int main()
198: #endif
199: {
200: unsigned int num;
201:
202: for (;;) {
203: printf("enter a number: ");
204: if (scanf("%u", &num))
205: printf("Next lower prime from %u is %u\n",
206: num, nlp(num));
207: else
208: break;
209: }
210:
211: return 0;
212: }
213: #endif /* TEST */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.