home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10242 < prev    next >
Encoding:
Internet Message Format  |  1992-08-13  |  2.2 KB
  1. Path: sparky!uunet!gatech!rpi!zaphod.mps.ohio-state.edu!caen!kuhub.cc.ukans.edu!husc-news.harvard.edu!ramanujan!elkies
  2. Newsgroups: sci.math
  3. Subject: Re: Erthstns' Sv
  4. Message-ID: <1992Aug13.173725.14705@husc3.harvard.edu>
  5. From: elkies@ramanujan.harvard.edu (Noam Elkies)
  6. Date: 13 Aug 92 17:37:24 EDT
  7. References: <1992Aug12.224159.14681@husc3.harvard.edu>
  8. Distribution: world
  9. Organization: Harvard Math Department
  10. Nntp-Posting-Host: ramanujan.harvard.edu
  11. Lines: 48
  12.  
  13. In article <1992Aug12.224159.14681@husc3.harvard.edu> O wrote:
  14. >Some years ago I read of a variation of Erathostenes' Sieve that
  15. >manages to compute the primes up to N in time o(N) [perhaps order
  16. >N/log(log(N))?] by compressing the sieve using the first few
  17. >primes (e.g. pre-sifting the multiples of 2,3,5,7 so one is
  18. >dealing with only 1*2*4*6=48 potential primes out of every
  19. >2*3*5*7=210 integers).  Unfortunately I have lost the reference.
  20. >Can any member of the computational number theory contingent on
  21. >sci.math provide a pointer to this paper?
  22.  
  23. Thanks to all who replied.  I have six references now, which should
  24. be plenty.  I list them below, each one with the respondent who first
  25. suggested it.
  26.  
  27. --Noam D. Elkies (elkies@zariski.harvard.edu)
  28.  Dept. of Mathematics, Harvard University
  29.  
  30. SvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSvSv
  31.  
  32. [From Todd Fine (fine@sctc.com):]
  33.  
  34. Some New Upper Bounds on the Generation of Prime Numbers, Harry G. Mairson,
  35. Communications of the ACM, September 1977, Volume 20, Number 9.
  36.  
  37. A Linear Sieve Algorithm for Finding Prime Numbers, David Gries and
  38. Jayadev Misra, Communications of the ACM, December 1978.
  39.  
  40. A Sublinear Additive Sieve for Finding Prime Numbers, Paul Pritchard,
  41. Communications of the ACM, January 1981, Volume 24, Number 1.
  42.  
  43.  
  44. [From Jeff Shallit (shallit@graceland.uwaterloo.ca):]
  45.  
  46. Paul Pritchard:
  47.  
  48. Explaining the wheel sieve, Acta. Infor. 17 (1982), 477-485.
  49.  
  50. A sublinear sieve for finding prime numbers, Comm. ACM 24 (1981), 18-23.
  51. Corrigenda, 24 (1981) 772.
  52.  
  53. Linear prime number sieves:  a family tree. 
  54. Sci. Computer Prog. 9 (1987), 17-35.
  55.  
  56.  
  57. [From Andrew Odlyzko (amo@research.att.com):]
  58.  
  59. Fast compact prime number sieves (among others),
  60. {\em J. Algorithms 4} (1983), 332--344.
  61.