home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10195 < prev    next >
Encoding:
Internet Message Format  |  1992-08-12  |  1.0 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!rpi!usenet.coe.montana.edu!news.u.washington.edu!ogicse!das-news.harvard.edu!husc-news.harvard.edu!ramanujan!elkies
  2. From: elkies@ramanujan.harvard.edu (Noam Elkies)
  3. Newsgroups: sci.math
  4. Subject: Erthstns' Sv
  5. Message-ID: <1992Aug12.224159.14681@husc3.harvard.edu>
  6. Date: 13 Aug 92 02:41:59 GMT
  7. Article-I.D.: husc3.1992Aug12.224159.14681
  8. Distribution: world
  9. Organization: Harvard Math Department
  10. Lines: 12
  11. Nntp-Posting-Host: ramanujan.harvard.edu
  12.  
  13. Some years ago I read of a variation of Erathostenes' Sieve that
  14. manages to compute the primes up to N in time o(N) [perhaps order
  15. N/log(log(N))?] by compressing the sieve using the first few
  16. primes (e.g. pre-sifting the multiples of 2,3,5,7 so one is
  17. dealing with only 1*2*4*6=48 potential primes out of every
  18. 2*3*5*7=210 integers).  Unfortunately I have lost the reference.
  19. Can any member of the computational number theory contingent on
  20. sci.math provide a pointer to this paper?
  21.  
  22. Thanks,
  23. --Noam D. Elkies (elkies@zariski.harvard.edu)
  24.   Dept. of Mathematics, Harvard University
  25.