Ulrich Drepper | b08d5a8 | 2005-07-26 05:00:05 +0000 | [diff] [blame^] | 1 | /* Determine prime number. |
| 2 | Copyright (C) 2000, 2002 Free Software Foundation, Inc. |
| 3 | Written by Ulrich Drepper <drepper@redhat.com>, 2000. |
| 4 | |
| 5 | This program is free software; you can redistribute it and/or modify |
| 6 | it under the terms of the GNU General Public License as published by |
| 7 | the Free Software Foundation, version 2. |
| 8 | |
| 9 | This program 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 General Public License for more details. |
| 13 | |
| 14 | You should have received a copy of the GNU General Public License |
| 15 | along with this program; if not, write to the Free Software Foundation, |
| 16 | Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ |
| 17 | |
| 18 | #include <stddef.h> |
| 19 | |
| 20 | |
| 21 | /* Test whether CANDIDATE is a prime. */ |
| 22 | static int |
| 23 | is_prime (size_t candidate) |
| 24 | { |
| 25 | /* No even number and none less than 10 will be passed here. */ |
| 26 | size_t divn = 3; |
| 27 | size_t sq = divn * divn; |
| 28 | |
| 29 | while (sq < candidate && candidate % divn != 0) |
| 30 | { |
| 31 | size_t old_sq = sq; |
| 32 | ++divn; |
| 33 | sq += 4 * divn; |
| 34 | if (sq < old_sq) |
| 35 | return 1; |
| 36 | ++divn; |
| 37 | } |
| 38 | |
| 39 | return candidate % divn != 0; |
| 40 | } |
| 41 | |
| 42 | |
| 43 | /* We need primes for the table size. */ |
| 44 | size_t |
| 45 | next_prime (size_t seed) |
| 46 | { |
| 47 | /* Make it definitely odd. */ |
| 48 | seed |= 1; |
| 49 | |
| 50 | while (!is_prime (seed)) |
| 51 | seed += 2; |
| 52 | |
| 53 | return seed; |
| 54 | } |