Is there a better way to find the nth prime?

조회 수: 14(최근 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
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개)

범주

Find more on Discrete Math in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by