home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3565 < prev    next >
Encoding:
Internet Message Format  |  1993-01-24  |  2.3 KB
  1. Path: sparky!uunet!cs.utexas.edu!asuvax!ncar!noao!amethyst!organpipe.uug.arizona.edu!news
  2. From: dave@cs.arizona.edu (Dave Schaumann)
  3. Newsgroups: comp.programming
  4. Subject: Re: how about PRIME numbers ?
  5. Message-ID: <1993Jan24.055343.2392@organpipe.uug.arizona.edu>
  6. Date: 24 Jan 93 05:53:43 GMT
  7. References: <peterd.727578786@tscc2>
  8. Sender: news@organpipe.uug.arizona.edu
  9. Reply-To: dave@cs.arizona.edu (Dave Schaumann)
  10. Organization: University of Arizona
  11. Lines: 53
  12. In-Reply-To: peterd@tscc2.macarthur.uws.edu.au
  13.  
  14. In article <peterd.727578786@tscc2>, peterd@tscc2 writes:
  15. >Ok, I asked for an algorithm for PI (and got several responses - thank you)
  16. >
  17. >How about an efficent algorithm for PRIME numbers ?
  18.  
  19. Well, for generating lists of 'em, there's always the Sieve of
  20. Erasthonese (sp?).  Not especially fast, but you really only need
  21. to run it once...
  22.  
  23. For testing primality (or prime factoring), here's a fairly obvious
  24. algorithm I came up with a long time ago:
  25.  
  26.  
  27. int is_prime( unsigned long n ) {
  28.  
  29.   unsigned long i, max = sqrt(n) ;
  30.  
  31.   if( n <= 3 ) return 1 ;
  32.  
  33.   if( n % 2 == 0 || n % 3 == 0 ) return 0 ;
  34.   for( i = 6 ; i <= max+1 ; i += 6 )
  35.     if( n % (i-1) == 0 || n % (i+1) == 0 ) return 0 ;
  36.  
  37.   return 1 ;
  38.   }
  39.  
  40. This works on two observations:
  41.  
  42.   1. If a number is not prime, it must have a factor less than or
  43.      equal to its square root.
  44.  
  45.   2. Once you've checked for division by 2 and 3, there is a simple
  46.      pattern for checking every 2 out of 6 possibilities thereafter
  47.      (similar to the way once you check for division by 2, you only
  48.      need to check for division by odd numbers)
  49.  
  50. Theoretically, the second observation could be extended to include
  51. more prime factors.  In practice, the pattern of candidate divisors
  52. is much more complicated (eg, for 5, the pattern length is 2*3*5=30
  53. numbers long), and the actual savings is increasingly small.
  54.  
  55. On the other hand, this seems reasonably adequate.  On a (lightly
  56. loaded) Sequent Symmetry, I used this algorithm to find the 194
  57. primes between 0xfffff000 and 0xffffffff (inclusive) in just over
  58. 20 seconds.
  59.  
  60. I'm not sure that you can do better than this; I believe that there
  61. is at least one encryption method based on the fact that factoring
  62. very large numbers is highly time-consuming (ie, not practical beyond
  63. a certain point).
  64.  
  65. -- 
  66. Dave Schaumann            dave@cs.arizona.edu
  67.