home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume18 / mcqueer-lib / prime.c < prev    next >
Encoding:
Text File  |  1989-11-09  |  1.5 KB  |  70 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(i)
  17. int i;
  18. {
  19.     if (i <= 2)
  20.         return (2);
  21.     if ((i%2) == 0)
  22.         ++i;
  23.     while (! is_prime(i))
  24.         i += 2;
  25.     return (i);
  26. }
  27.  
  28. /*
  29. ** simply check all factors <= the square root of the number, with
  30. ** a minor wrinkle:
  31. **
  32. ** we split our checks into two separate chains which cover all
  33. ** numbers with no factors of 2 or 3, avoiding many of the non-
  34. ** prime factors.  factor1 winds up being all integers = 5 mod 6,
  35. ** factor2 all integers >= 7 which = 1 mod 6.  Anything = 0,2,3 or
  36. ** 4 mod 6 divides by 2 or 3.
  37. **
  38. ** this gives a rather small number of redundant factor checks for
  39. ** reasonable sized arguments (say < 10000).  Only for extremely large
  40. ** numbers would the extra overhead justify a "smarter" algorithm.
  41. **
  42. ** only valid for i >= 2.
  43. */
  44. int
  45. is_prime(i)
  46. int i;
  47. {
  48.     int factor1,factor2;
  49.  
  50.     if (i == 2 || i == 3)
  51.         return(1);
  52.  
  53.     if ((i%3) == 0 || (i%2) == 0)
  54.         return(0);
  55.  
  56.     factor1 = 5;
  57.     factor2 = 7;
  58.     while ((factor1 * factor1) <= i)
  59.     {
  60.         if ((i % factor1) == 0)
  61.             return (0);
  62.         if ((i % factor2) == 0)
  63.             return (0);
  64.         factor1 += 6;
  65.         factor2 += 6;
  66.     }
  67.  
  68.     return (1);
  69. }
  70.