Is there a better way to find the nth prime?

3 次查看（过去 30 天）
Andrew Chen
Andrew Chen 2016-9-14
编辑： Walter Roberson 2016-9-14
I want to find the value of the nth prime number. For example, the 10th prime number is 29. My code currently looks like this:
n = 1;
x = 10001;
while sum(isprime(primes(n)))<x
n = n + 1;
end
n
I want to find the 10001st prime number (x = 10001), however this takes quite a while since the while loop executes for each natural number until 10001 primes have been counted. Is there a more efficient to write this code so that it doe's not take so long to execute? Thanks in advance.

请先登录，再回答此问题。

采纳的回答

Walter Roberson
Walter Roberson 2016-9-14
Just as an obvious change:
n = 1;
x = 10001;
while length(primes(n)))<x
n = n + 1;
end
n
This can definitely be improved still further.
  3 个评论
显示 1更早的评论
Walter Roberson
Walter Roberson 2016-9-14
Yes. The output of primes() are guaranteed to be primes, so there is no point in using isprime() on them -- that is just wasted cycles.
Walter Roberson
Walter Roberson 2016-9-14
编辑：Walter Roberson 2016-9-14
Hint: You do not need to increment n by only 1 at a time: if you overshoot then you can just take the x'th element of the result of primes(n)
In particular, there are ways to estimate how far you will need to go: https://en.wikipedia.org/wiki/Prime-counting_function

请先登录，再进行评论。

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Discrete Math 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by