| 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 |
} |