On Wed, Apr 2, 2014 at 1:20 PM, Szabolcs Horvát <[email protected]> wrote: > Hello, > > I'm quite new to Sage. Does it have any functionality that will easily > compute the Nth prime and it's fast enough that it will work for N of the > order 10^9 or 10^10 reasonable quickly (say, under 10 seconds)? > > pari.nth_prime(1000000000) takes a very long time. > > Are there alternatives?
You could get an estimate for an x such pi(x) ~ N using Li(x) (and of course assuming RH). Then use prime_pi in Sage, which is vastly faster than nth_prime to iteratively adjust x until you find N or something close -- once close, just start doing primality testing which is fast around this range. In the range where pari.nth_prime is taking 20-30 seconds, prime_pi is much, must faster, so this might work. The above strategy isn't implemented. You'll have to implement it. I'm not sure if it works well or not, but it is what I would do. It should be easy to implement, and you should submit the result for inclusion in sage. By the way, prime_pi is faster than pari because it is Cython-code-from-scratch that Andrew Ohana wrote for Sage as part of an undergrad student project. It is not asymptotically the fastest, but in the range you care about it is useful. William > > Szabolcs > > -- > You received this message because you are subscribed to the Google Groups > "sage-support" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > Visit this group at http://groups.google.com/group/sage-support. > For more options, visit https://groups.google.com/d/optout. -- William Stein Professor of Mathematics University of Washington http://wstein.org -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
