src/libs/libgroff/prime.cpp

   1 /* Copyright (C) 2014-2018 Free Software Foundation, Inc.
   2
   3 This file is part of groff.
   4
   5 groff is free software; you can redistribute it and/or modify it under
   6 the terms of the GNU General Public License as published by the Free
   7 Software Foundation, either version 2 of the License, or
   8 (at your option) any later version.
   9
  10 groff is distributed in the hope that it will be useful, but WITHOUT ANY
  11 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13 for more details.
  14
  15 The GNU General Public License version 2 (GPL2) is available in the
  16 internet at <http://www.gnu.org/licenses/gpl-2.0.txt>. */
  17
  18 #ifdef HAVE_CONFIG_H
  19 #include "config.h"
  20 #endif
  21 #include <math.h>
  22
  23 int is_prime(unsigned n)
  24 {
  25   if (n <= 3)
  26     return 1;
  27   if (!(n & 1))
  28     return 0;
  29   if (n % 3 == 0)
  30     return 0;
  31   unsigned lim = unsigned(sqrt((double)n));
  32   unsigned d = 5;
  33   for (;;) {
  34     if (d > lim)
  35       break;
  36     if (n % d == 0)
  37       return 0;
  38     d += 2;
  39     if (d > lim)
  40       break;
  41     if (n % d == 0)
  42       return 0;
  43     d += 4;
  44   }
  45   return 1;
  46 }