Line data    Source code

       1             : /* Copyright 2014-2020 Free Software Foundation, Inc.
       2             : 
       3             : This file is part of groff, the GNU roff typesetting system.
       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             : 
      22             : #include <assert.h>
      23             : #include <math.h>
      24             : 
      25             : static bool is_prime(unsigned);
      26             : 
      27           0 : unsigned ceil_prime(unsigned n)
      28             : {
      29           0 :   if (n <= 2)
      30           0 :     return 2;
      31             : 
      32           0 :   if (n % 2 == 0)
      33           0 :     n++;
      34             : 
      35           0 :   while (!is_prime(n))
      36           0 :     n += 2;
      37             : 
      38           0 :   return n;
      39             : }
      40             : 
      41           0 : static bool is_prime(unsigned n)
      42             : {
      43           0 :   assert(n > 1);
      44           0 :   if (n <= 3)
      45           0 :     return true;
      46           0 :   if (!(n & 1))
      47           0 :     return false;
      48           0 :   if (n % 3 == 0)
      49           0 :     return false;
      50           0 :   unsigned lim = unsigned(sqrt((double)n));
      51           0 :   unsigned d = 5;
      52             :   for (;;) {
      53           0 :     if (d > lim)
      54           0 :       break;
      55           0 :     if (n % d == 0)
      56           0 :       return false;
      57           0 :     d += 2;
      58           0 :     if (d > lim)
      59           0 :       break;
      60           0 :     if (n % d == 0)
      61           0 :       return false;
      62           0 :     d += 4;
      63             :   }
      64           0 :   return true;
      65             : }
      66             : 
      67             : // Local Variables:
      68             : // fill-column: 72
      69             : // mode: C++
      70             : // End:
      71             : // vim: set cindent noexpandtab shiftwidth=2 textwidth=72: