Is there a better way to find the nth prime?
조회 수: 4 (최근 30일)
이전 댓글 표시
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.
댓글 수: 0
채택된 답변
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
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
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!