home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 15 / CDACTUAL15.iso / cdactual / program / asm / LMPRIME1.ZIP / PRIMES14.ZIP / PRIMES14.DOC < prev   
Encoding:
Text File  |  1991-10-29  |  2.9 KB  |  66 lines
  1.  
  2.                  Prime Solutions Version 1.4
  3.  
  4.                   (c) 1991 William C. Parke
  5.  
  6. The program PRIMES generates the prime numbers from 1 to 1,048,559,
  7. starting with a code containing no more than about 1,000 bytes. It was
  8. stimulated by a Spring, 1991 contest by Howard Mencher on the
  9. Programmer's Corner (Gary Smith's BBS) in Washington, D.C.  (Columbia,
  10. MD). PRIMES was written to demonstrate both the economy and speed of
  11. programs written in assembly. [Howard's contest specifically excluded
  12. ASM code.]
  13.  
  14. The calculation of the primes to 1,048,573 takes less than two seconds
  15. on a 25MHz '386 machine, although printing them to the screen requires a
  16. significantly longer time.  Screen-print time could be reduced by a
  17. factor of 1/3 using direct screen video functions. However, this option
  18. would prevent redirected to a file using the DOS command line
  19. redirection function.  Of course, another strategy for generating primes
  20. is to store information about their distribution in the data area of the
  21. program.  This would allow a faster initialization. However, it requires
  22. significantly more disk space, goes against the requirement of
  23. calculating the primes in the first place, and would not be necessary
  24. even in practice.
  25.  
  26. There are 82,025 primes from 1 to 1,048,575.  (The number of primes
  27. between 1 and N is approximately  N/lnN for large N.)  A bit map for all
  28. these takes no more than 64K bytes.  Thus, it would be possible to
  29. generate and store this prime number table within the data area of a
  30. code which needed primes, such as a factorization algorithm.  [The bit
  31. map table itself contains significant redundant information. The ZIP
  32. compression reduces the table by 24%. A formula for any prime would take
  33. up far less space!]  Note, however, that the application of prime number
  34. divisions to factorize large numbers is not practical when the number of
  35. digits approaches 50 or more. (For some practical alternatives, see
  36. Knuth, Seminumerical Algorithms, Vol.2 in The Art of Computer
  37. Programming, Second Edition, Addison Wesley, 1981.)
  38.  
  39. The syntax for running PRIMES is
  40.  
  41.         PRIMES n1 n2
  42.  
  43.     where n1 and n2 are decimal digits (no comma delimitors)
  44.     with 0 < n1 < n2 < 1048576.
  45.  
  46. For example,
  47.  
  48.         PRIMES 10237 10313
  49.  
  50. will show the primes between these given numbers, inclusive.
  51.  
  52. The program will also display a count of the number of primes found.
  53.  
  54. To make a file of the primes, use DOS redirection.  For example
  55.  
  56.         PRIMES 1 100,000 > PRIM4
  57.  
  58. will make a file called PRIM4 with the primes from 1 to 100,000.
  59.  
  60. History:
  61.   Version 1.4 Sped up prime calculation by stopping sieve at square
  62.               root of larger prime; corrected bug found by Les Moskowitz.
  63.   Version 1.3 drops printing of 2 for large n1.  ASM files are included.
  64.   Version 1.2 differs from 1.1 by correcting the first prime as 2 rather
  65.               than 1, and fixes a bug in PRIMES.
  66.