src/libs/libgroff/prime.cpp

   1 /* Copyright (C) 2014  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 #include <math.h>
  19
  20 int is_prime(unsigned n)
  21 {
  22   if (n <= 3)
  23     return 1;
  24   if (!(n & 1))
  25     return 0;
  26   if (n % 3 == 0)
  27     return 0;
  28   unsigned lim = unsigned(sqrt((double)n));
  29   unsigned d = 5;
  30   for (;;) {
  31     if (d > lim)
  32       break;
  33     if (n % d == 0)
  34       return 0;
  35     d += 2;
  36     if (d > lim)
  37       break;
  38     if (n % d == 0)
  39       return 0;
  40     d += 4;
  41   }
  42   return 1;
  43 }