home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11219 < prev    next >
Encoding:
Internet Message Format  |  1992-09-10  |  1.4 KB
  1. Path: sparky!uunet!mcsun!uknet!pavo.csi.cam.ac.uk!gjm11
  2. From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
  3. Newsgroups: sci.math
  4. Subject: Re: nth prime
  5. Message-ID: <1992Sep10.164133.27763@infodev.cam.ac.uk>
  6. Date: 10 Sep 92 16:41:33 GMT
  7. References: <1992Sep10.190905.10741@waikato.ac.nz>
  8. Sender: news@infodev.cam.ac.uk (USENET news)
  9. Organization: U of Cambridge, England
  10. Lines: 18
  11. Nntp-Posting-Host: apus.cus.cam.ac.uk
  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. you do n/2 things, and in [... er, we're suddenly working out the
  21. biggest prime less than n. This is of equal complexity...] total
  22. we do n(1/2+1/3+...+1/p) things, where p is the biggest prime less
  23. than root(n). Now it's well known that the series there comes to
  24. about log log root(n). So the time for "primes up to n" is about
  25. n log log n, and so the time for "nth prime" is about
  26. (n log n) log log (n log n), which is about n log n log log n.
  27. As I say, I don't think you can do much better than this.
  28. -- 
  29. Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
  30. gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]
  31.