home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11240 < prev    next >
Encoding:
Internet Message Format  |  1992-09-10  |  1.5 KB
  1. Path: sparky!uunet!paladin.american.edu!darwin.sura.net!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!cbnewse!cbnewsd!att-out!pacbell.com!network.ucsd.edu!mvb.saic.com!unogate!beckman.com!dn66!a_rubin
  2. Newsgroups: sci.math
  3. Subject: Re: nth prime
  4. Message-ID: <a_rubin.716166518@dn66>
  5. From: a_rubin@dsg4.dse.beckman.com (Arthur Rubin)
  6. Date: 10 Sep 92 23:08:38 GMT
  7. References: <1992Sep10.190905.10741@waikato.ac.nz> <1992Sep10.164133.27763@infodev.cam.ac.uk>
  8. Nntp-Posting-Host: dn66.dse.beckman.com
  9. Lines: 20
  10.  
  11. In <1992Sep10.164133.27763@infodev.cam.ac.uk> gjm11@cus.cam.ac.uk (G.J. McCaughan) writes:
  12.  
  13. >In article <1992Sep10.190905.10741@waikato.ac.nz> bill@waikato.ac.nz writes:
  14.  
  15. >>Sorry to ask such a FAQ, but what's the quickest algorithm to
  16. >>find the nth prime? Is it O(nlogn) or something else?
  17.  
  18. >I think there is no way to get p_n exactly that's much better than
  19. >the good old sieve of Eratosthenes. So in sieving out multiples of 2
  20. ...
  21.  
  22. This isn't quite correct.  There is an integral for (the number of primes
  23. <= n) which takes o(n) to evaluate.  (I don't know the exact order.)  I'm
  24. pretty sure that the time to find the first n primes is about  O(n log n),
  25. but you don't have to all n of them in order to find the n_th.
  26. --
  27. Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
  28. 216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
  29. My opinions are my own, and do not represent those of my employer.
  30. My interaction with our news system is unstable; please mail anything important.
  31.