125b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* Determine prime number. 225b3c049e70834cf33790a28643ab058b507b35cBen Cheng Copyright (C) 2006 Red Hat, Inc. 303333823c75a1c1887e923828113a1b0fd12020cElliott Hughes This file is part of elfutils. 425b3c049e70834cf33790a28643ab058b507b35cBen Cheng Written by Ulrich Drepper <drepper@redhat.com>, 2000. 525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 603333823c75a1c1887e923828113a1b0fd12020cElliott Hughes This file is free software; you can redistribute it and/or modify 703333823c75a1c1887e923828113a1b0fd12020cElliott Hughes it under the terms of either 825b3c049e70834cf33790a28643ab058b507b35cBen Cheng 903333823c75a1c1887e923828113a1b0fd12020cElliott Hughes * the GNU Lesser General Public License as published by the Free 1003333823c75a1c1887e923828113a1b0fd12020cElliott Hughes Software Foundation; either version 3 of the License, or (at 1103333823c75a1c1887e923828113a1b0fd12020cElliott Hughes your option) any later version 1203333823c75a1c1887e923828113a1b0fd12020cElliott Hughes 1303333823c75a1c1887e923828113a1b0fd12020cElliott Hughes or 1403333823c75a1c1887e923828113a1b0fd12020cElliott Hughes 1503333823c75a1c1887e923828113a1b0fd12020cElliott Hughes * the GNU General Public License as published by the Free 1603333823c75a1c1887e923828113a1b0fd12020cElliott Hughes Software Foundation; either version 2 of the License, or (at 1703333823c75a1c1887e923828113a1b0fd12020cElliott Hughes your option) any later version 1803333823c75a1c1887e923828113a1b0fd12020cElliott Hughes 1903333823c75a1c1887e923828113a1b0fd12020cElliott Hughes or both in parallel, as here. 2003333823c75a1c1887e923828113a1b0fd12020cElliott Hughes 2103333823c75a1c1887e923828113a1b0fd12020cElliott Hughes elfutils is distributed in the hope that it will be useful, but 2225b3c049e70834cf33790a28643ab058b507b35cBen Cheng WITHOUT ANY WARRANTY; without even the implied warranty of 2325b3c049e70834cf33790a28643ab058b507b35cBen Cheng MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 2425b3c049e70834cf33790a28643ab058b507b35cBen Cheng General Public License for more details. 2525b3c049e70834cf33790a28643ab058b507b35cBen Cheng 2603333823c75a1c1887e923828113a1b0fd12020cElliott Hughes You should have received copies of the GNU General Public License and 2703333823c75a1c1887e923828113a1b0fd12020cElliott Hughes the GNU Lesser General Public License along with this program. If 2803333823c75a1c1887e923828113a1b0fd12020cElliott Hughes not, see <http://www.gnu.org/licenses/>. */ 2925b3c049e70834cf33790a28643ab058b507b35cBen Cheng 3025b3c049e70834cf33790a28643ab058b507b35cBen Cheng#include <stddef.h> 3125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 3225b3c049e70834cf33790a28643ab058b507b35cBen Cheng 3325b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* Test whether CANDIDATE is a prime. */ 3425b3c049e70834cf33790a28643ab058b507b35cBen Chengstatic int 3525b3c049e70834cf33790a28643ab058b507b35cBen Chengis_prime (size_t candidate) 3625b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 3725b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* No even number and none less than 10 will be passed here. */ 3825b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t divn = 3; 3925b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t sq = divn * divn; 4025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 4125b3c049e70834cf33790a28643ab058b507b35cBen Cheng while (sq < candidate && candidate % divn != 0) 4225b3c049e70834cf33790a28643ab058b507b35cBen Cheng { 4325b3c049e70834cf33790a28643ab058b507b35cBen Cheng size_t old_sq = sq; 4425b3c049e70834cf33790a28643ab058b507b35cBen Cheng ++divn; 4525b3c049e70834cf33790a28643ab058b507b35cBen Cheng sq += 4 * divn; 4625b3c049e70834cf33790a28643ab058b507b35cBen Cheng if (sq < old_sq) 4725b3c049e70834cf33790a28643ab058b507b35cBen Cheng return 1; 4825b3c049e70834cf33790a28643ab058b507b35cBen Cheng ++divn; 4925b3c049e70834cf33790a28643ab058b507b35cBen Cheng } 5025b3c049e70834cf33790a28643ab058b507b35cBen Cheng 5125b3c049e70834cf33790a28643ab058b507b35cBen Cheng return candidate % divn != 0; 5225b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 5325b3c049e70834cf33790a28643ab058b507b35cBen Cheng 5425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 5525b3c049e70834cf33790a28643ab058b507b35cBen Cheng/* We need primes for the table size. */ 5625b3c049e70834cf33790a28643ab058b507b35cBen Chengsize_t 5725b3c049e70834cf33790a28643ab058b507b35cBen Chengnext_prime (size_t seed) 5825b3c049e70834cf33790a28643ab058b507b35cBen Cheng{ 5925b3c049e70834cf33790a28643ab058b507b35cBen Cheng /* Make it definitely odd. */ 6025b3c049e70834cf33790a28643ab058b507b35cBen Cheng seed |= 1; 6125b3c049e70834cf33790a28643ab058b507b35cBen Cheng 6225b3c049e70834cf33790a28643ab058b507b35cBen Cheng while (!is_prime (seed)) 6325b3c049e70834cf33790a28643ab058b507b35cBen Cheng seed += 2; 6425b3c049e70834cf33790a28643ab058b507b35cBen Cheng 6525b3c049e70834cf33790a28643ab058b507b35cBen Cheng return seed; 6625b3c049e70834cf33790a28643ab058b507b35cBen Cheng} 67