home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11235 < prev    next >
Encoding:
Internet Message Format  |  1992-09-10  |  1.5 KB
  1. Path: sparky!uunet!mcsun!uknet!pavo.csi.cam.ac.uk!camcus!gjm11
  2. From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
  3. Newsgroups: sci.math
  4. Subject: Re: nth prime
  5. Message-ID: <1992Sep10.231742.573@infodev.cam.ac.uk>
  6. Date: 10 Sep 92 23:17:42 GMT
  7. References: <1992Sep10.190905.10741@waikato.ac.nz> <1992Sep10.164133.27763@infodev.cam.ac.uk>
  8. Sender: news@infodev.cam.ac.uk (USENET news)
  9. Organization: U of Cambridge, England
  10. Lines: 20
  11. Nntp-Posting-Host: apus.cus.cam.ac.uk
  12.  
  13. In article <1992Sep10.164133.27763@infodev.cam.ac.uk>, gjm11@cus.cam.ac.uk (me) wrote:
  14.  
  15. > I think there is no way to get p_n exactly that's much better than
  16. > the good old sieve of Eratosthenes.
  17.  
  18. Ahem. As has been pointed out to me, this is quite false. There are quicker
  19. ways to calculate exactly the number of primes less than n (there's a method
  20. due to Legendre that takes time about n^(2/3), and the person who pointed out
  21. my mistake thinks there may be a method that takes only n^(3/5)), and then
  22. [this is what I missed!] you can do a binary search thing, which is going to
  23. take not more than about log n iterations of the prime-counting procedure.
  24. So, YES: you can calculate the n'th prime in time about n^t, for some t which
  25. might be as small as 3/5 but is certainly no worse than 2/3. ("About" here
  26. means that you can do it in time O(n^(t+epsilon)) whenever epsilon>0, if
  27. you're being picky.)
  28.  
  29. I can probably find a reference to the Legendre method if you want.
  30. -- 
  31. Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
  32. gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]
  33.