1 /* Determine prime number. 2 Copyright (C) 2000, 2002 Free Software Foundation, Inc. 3 Written by Ulrich Drepper <drepper (at) 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 } 55
