Debian Codegraph @

lib/next-prime.c

raw
1 /* Finding the next prime >= a given small integer.
2 Copyright (C) 1995-2026 Free Software Foundation, Inc.
3
4 This file is free software: you can redistribute it and/or modify
5 it under the terms of the GNU Lesser General Public License as
6 published by the Free Software Foundation; either version 2.1 of the
7 License, or (at your option) any later version.
8
9 This file is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU Lesser General Public License for more details.
13
14 You should have received a copy of the GNU Lesser General Public License
15 along with this program. If not, see <https://www.gnu.org/licenses/>. */
16
17 #include <config.h>
18
19 /* Specification. */
20 #include "next-prime.h"
21
22 #include <stdint.h> /* for SIZE_MAX */
23
24 /* Return true if CANDIDATE is a prime number or 1.
25 CANDIDATE should be an odd number >= 1. */
26 static bool _GL_ATTRIBUTE_CONST
27 is_prime (size_t candidate)
28 {
29 size_t divisor = 3;
30 size_t square = divisor * divisor;
31
32 for (;;)
33 {
34 if (square > candidate)
35 return true;
36 if ((candidate % divisor) == 0)
37 return false;
38 /* Increment divisor by 2. */
39 divisor++;
40 square += 4 * divisor;
41 divisor++;
42 }
43 }
44
45 size_t _GL_ATTRIBUTE_CONST
46 next_prime (size_t candidate)
47 {
48 #if !defined IN_LIBGETTEXTLIB
49 /* Skip small primes. */
50 if (candidate < 10)
51 candidate = 10;
52 #endif
53
54 /* Make it definitely odd. */
55 candidate |= 1;
56
57 while (SIZE_MAX != candidate && !is_prime (candidate))
58 candidate += 2;
59
60 return candidate;
61 }