Branch data Line data Source code
1 : : /* Determine prime number.
2 : : Copyright (C) 2006 Red Hat, Inc.
3 : : This file is part of elfutils.
4 : : Written by Ulrich Drepper <drepper@redhat.com>, 2000.
5 : :
6 : : This file is free software; you can redistribute it and/or modify
7 : : it under the terms of either
8 : :
9 : : * the GNU Lesser General Public License as published by the Free
10 : : Software Foundation; either version 3 of the License, or (at
11 : : your option) any later version
12 : :
13 : : or
14 : :
15 : : * the GNU General Public License as published by the Free
16 : : Software Foundation; either version 2 of the License, or (at
17 : : your option) any later version
18 : :
19 : : or both in parallel, as here.
20 : :
21 : : elfutils is distributed in the hope that it will be useful, but
22 : : WITHOUT ANY WARRANTY; without even the implied warranty of
23 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
24 : : General Public License for more details.
25 : :
26 : : You should have received copies of the GNU General Public License and
27 : : the GNU Lesser General Public License along with this program. If
28 : : not, see <http://www.gnu.org/licenses/>. */
29 : :
30 : : #ifdef HAVE_CONFIG_H
31 : : # include <config.h>
32 : : #endif
33 : :
34 : : #include <stddef.h>
35 : :
36 : :
37 : : /* Test whether CANDIDATE is a prime. */
38 : : static int
39 : 127456 : is_prime (size_t candidate)
40 : : {
41 : : /* No even number and none less than 10 will be passed here. */
42 : 127456 : size_t divn = 3;
43 : 127456 : size_t sq = divn * divn;
44 : :
45 [ + + + + ]: 437748 : while (sq < candidate && candidate % divn != 0)
46 : : {
47 : 310292 : size_t old_sq = sq;
48 : 310292 : ++divn;
49 : 310292 : sq += 4 * divn;
50 [ + - ]: 310292 : if (sq < old_sq)
51 : : return 1;
52 : 310292 : ++divn;
53 : : }
54 : :
55 : 127456 : return candidate % divn != 0;
56 : : }
57 : :
58 : :
59 : : /* We need primes for the table size. */
60 : : size_t
61 : 127342 : next_prime (size_t seed)
62 : : {
63 : : /* Make it definitely odd. */
64 : 127342 : seed |= 1;
65 : :
66 [ + + ]: 127456 : while (!is_prime (seed))
67 : 114 : seed += 2;
68 : :
69 : 127342 : return seed;
70 : : }
|