home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11266 < prev    next >
Encoding:
Text File  |  1992-09-11  |  3.4 KB  |  70 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!newsgate.watson.ibm.com!yktnews!admin!yktnews!victor
  3. From: victor@watson.ibm.com (Victor Miller)
  4. Subject: Re: nth prime
  5. Sender: news@watson.ibm.com (NNTP News Poster)
  6. Message-ID: <VICTOR.92Sep11100049@terse4.watson.ibm.com>
  7. In-Reply-To: a_rubin@dsg4.dse.beckman.com's message of 10 Sep 92 23:08:38 GMT
  8. Date: Fri, 11 Sep 1992 14:00:49 GMT
  9. Reply-To: victor@watson.ibm.com
  10. Disclaimer: This posting represents the poster's views, not necessarily those of IBM
  11. References: <1992Sep10.190905.10741@waikato.ac.nz>
  12.     <1992Sep10.164133.27763@infodev.cam.ac.uk> <a_rubin.716166518@dn66>
  13. Nntp-Posting-Host: terse4.watson.ibm.com
  14. Organization: IBM, T.J. Watson Research Center
  15. Lines: 53
  16.  
  17. >>>>> On 10 Sep 92 23:08:38 GMT, a_rubin@dsg4.dse.beckman.com (Arthur Rubin) said:
  18.  
  19. Arthur> In <1992Sep10.164133.27763@infodev.cam.ac.uk> gjm11@cus.cam.ac.uk (G.J. McCaughan) writes:
  20.  
  21. >In article <1992Sep10.190905.10741@waikato.ac.nz> bill@waikato.ac.nz writes:
  22.  
  23. >>Sorry to ask such a FAQ, but what's the quickest algorithm to
  24. >>find the nth prime? Is it O(nlogn) or something else?
  25.  
  26. >I think there is no way to get p_n exactly that's much better than
  27. >the good old sieve of Eratosthenes. So in sieving out multiples of 2
  28. Arthur> ...
  29.  
  30. Arthur> This isn't quite correct.  There is an integral for (the number of primes
  31. Arthur> <= n) which takes o(n) to evaluate.  (I don't know the exact order.)  I'm
  32. Arthur> pretty sure that the time to find the first n primes is about  O(n log n),
  33. Arthur> but you don't have to all n of them in order to find the n_th.
  34. Arthur> --
  35. Arthur> Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
  36. Arthur> 216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
  37. Arthur> My opinions are my own, and do not represent those of my employer.
  38. Arthur> My interaction with our news system is unstable; please mail anything important.
  39.  
  40. This keeps coming up (maybe it should be in the FAQ).  There are two
  41. different methods for evaluation pi(x) (the exact number of primes
  42. <=x).  One is a method based on combinatorial sieving.  The latest and
  43. greatest incarnation of that method is a paper "Calculating pi(x): the
  44. Meissel-Lehmer Method" by Jeff Lagarias, Victor Miller (that's me),
  45. and Anrew Odlyzko in Math. Comp. 1985.  It gives the history of this
  46. method.  Although it had its genesis in the observation of Legendre
  47. that one could get an explicit formula for pi(x) only involving primes
  48. <= sqrt(x), it needed substantial refinements to get to the running
  49. time of O(x^{2/3 + \epsilon}).  I programmed this method and used it
  50. to calculate the table of values given in the paper (up to x=4*10^16).
  51. Once one has a method of calculating pi(x) you can use binary search
  52. to caculate p_n (the n-th prime).  This adds a factor of log n.  Using
  53. interpolation search only adds a factor of log log n.
  54.  
  55. Lagarias and Odlyzko, in "Calculating pi(x): an Analytic Method" in J.
  56. of Algorithms, 1986, describe a method based on "explicit formulas in
  57. prime number theory" which has running time O(x^{3/5+\epsilon}) and
  58. space o(x).  Based an a subsequent paper by Odlyzko and Schonhage this
  59. running time can be gotten down to O(x^{1/2+\epsilon}) with space
  60. O(x^{1/4+\epsilon}).  This method is extremely subtle, and to my
  61. knowledge has never been implemented.
  62.  
  63.  
  64. --
  65.         Victor S. Miller
  66.         Bitnet: VICTOR at WATSON
  67.         Internet: victor@watson.ibm.com
  68.         IBM, TJ Watson Research Center
  69.         "Great artists steal; lesser artists borrow" Igor Stravinsky
  70.