home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11263 < prev    next >
Encoding:
Text File  |  1992-09-11  |  1.3 KB  |  29 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!mcsun!Germany.EU.net!news.uni-bielefeld.de!achim
  3. From: achim@unibi.uni-bielefeld.de (Achim Flammenkamp)
  4. Subject: Re: nth prime
  5. Message-ID: <1992Sep11.133129.23901@unibi.uni-bielefeld.de>
  6. Date: Fri, 11 Sep 92 13:31:29 GMT
  7. References: <1992Sep10.190905.10741@waikato.ac.nz>
  8. Organization: Universitaet Bielefeld
  9. Lines: 18
  10.  
  11. In article <1992Sep10.190905.10741@waikato.ac.nz> bill@waikato.ac.nz writes:
  12. >Sorry to ask such a FAQ, but what's the quickest algorithm to
  13. >find the nth prime? Is it O(nlogn) or something else?
  14. >
  15. I think it is not a FAQ :)
  16.  
  17. You have to calculate the "inverse function" of PI(n), the number of primes 
  18. less than n. There are clever algorithmns like the telescop method of Meissel
  19. to calculate PI(n) in time O(n^2/3). Look for a recent calculation in Math.
  20. of Computation about 1985 from Odlytzko (probably spelled wrong, sorry). They
  21. calculated PI(x) upto 4*10^16. Maybe today there are algorithmns availible
  22. which have a running time of n^k with 1/3<k<2/3. To get the nth-prime you have
  23. to too a binary search on PI(n) roughly spoken , order log(n). So you will
  24. get the nth-prime in about n^k which k <= 2/3.
  25. My personally opinion is that the theoritical bound is less than n^eps for
  26. each postive eps , but to find such an algorithmn you have to understand the
  27. prime distribution totally :)
  28. achim
  29.