]> mj.ucw.cz Git - libucw.git/blob - ucw/prime.c
The big move. Step #1: Move whole lib/ to ucw/.
[libucw.git] / ucw / prime.c
1 /*
2  *      UCW Library -- Prime Number Tests
3  *
4  *      (c) 1997 Martin Mares <mj@ucw.cz>
5  *
6  *      This software may be freely distributed and used according to the terms
7  *      of the GNU Lesser General Public License.
8  */
9
10 #include "ucw/lib.h"
11
12 static int                              /* Sequential search */
13 __isprime(uns x)                        /* We know x != 2 && x != 3 */
14 {
15   uns test = 5;
16
17   if (x == 5)
18     return 1;
19   for(;;)
20     {
21       if (!(x % test))
22         return 0;
23       if (x / test <= test)
24         return 1;
25       test += 2;                        /* 6k+1 */
26       if (!(x % test))
27         return 0;
28       if (x / test <= test)
29         return 1;
30       test += 4;                        /* 6k-1 */
31     }
32 }
33
34 int
35 isprime(uns x)
36 {
37   if (x < 5)
38     return (x == 2 || x == 3);
39   switch (x % 6)
40     {
41     case 1:
42     case 5:
43       return __isprime(x);
44     default:
45       return 0;
46     }
47 }
48
49 uns
50 nextprime(uns x)                        /* Returns some prime greater than x */
51 {
52   x += 5 - (x % 6);                     /* x is 6k-1 */
53   for(;;)
54     {
55       x += 2;                           /* 6k+1 */
56       if (__isprime(x))
57         return x;
58       x += 4;                           /* 6k-1 */
59       if (__isprime(x))
60         return x;
61     }
62 }
63
64 #ifdef TEST
65
66 #include <stdio.h>
67 #include <stdlib.h>
68
69 int
70 main(int argc, char **argv)
71 {
72   uns k = atol(argv[1]);
73   printf("%d is%s prime\n", k, isprime(k) ? "" : "n't");
74   printf("Next prime is %d\n", nextprime(k));
75   return 0;
76 }
77
78 #endif