home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume26 / ns2tab / part01 / prime.c < prev    next >
Encoding:
Text File  |  1993-04-04  |  1.5 KB  |  68 lines
  1. /*
  2. **
  3. **    Copyright (c) 1987, Robert L. McQueer
  4. **        All Rights Reserved
  5. **
  6. ** Permission granted for use, modification and redistribution of this
  7. ** software provided that no use is made for commercial gain without the
  8. ** written consent of the author, that all copyright notices remain intact,
  9. ** and that all changes are clearly documented.  No warranty of any kind
  10. ** concerning any use which may be made of this software is offered or implied.
  11. **
  12. */
  13.  
  14. /* return smallest prime >= i */
  15. int
  16. next_prime(int i)
  17. {
  18.     if (i <= 2)
  19.         return (2);
  20.     if ((i%2) == 0)
  21.         ++i;
  22.     while (! is_prime(i))
  23.         i += 2;
  24.     return (i);
  25. }
  26.  
  27. /*
  28. ** simply check all factors <= the square root of the number, with
  29. ** a minor wrinkle:
  30. **
  31. ** we split our checks into two separate chains which cover all
  32. ** numbers with no factors of 2 or 3, avoiding many of the non-
  33. ** prime factors.  factor1 winds up being all integers = 5 mod 6,
  34. ** factor2 all integers >= 7 which = 1 mod 6.  Anything = 0,2,3 or
  35. ** 4 mod 6 divides by 2 or 3.
  36. **
  37. ** this gives a rather small number of redundant factor checks for
  38. ** reasonable sized arguments (say < 10000).  Only for extremely large
  39. ** numbers would the extra overhead justify a "smarter" algorithm.
  40. **
  41. ** only valid for i >= 2.
  42. */
  43. int
  44. is_prime(int i)
  45. {
  46.     int factor1,factor2;
  47.  
  48.     if (i == 2 || i == 3)
  49.         return(1);
  50.  
  51.     if ((i%3) == 0 || (i%2) == 0)
  52.         return(0);
  53.  
  54.     factor1 = 5;
  55.     factor2 = 7;
  56.     while ((factor1 * factor1) <= i)
  57.     {
  58.         if ((i % factor1) == 0)
  59.             return (0);
  60.         if ((i % factor2) == 0)
  61.             return (0);
  62.         factor1 += 6;
  63.         factor2 += 6;
  64.     }
  65.  
  66.     return (1);
  67. }
  68.