Nth Prime and Sieve are redundant

Programming Rust
1

Both of these are essentially writing the same code, since you have to compute the first N primes with a sieve to find the nth prime.

2

The sieve of Eratosthenes is not the only possible algorithm to compute the nth prime.

3 Likes
3

Sieve requires knowing the upper limit of the number you’re trying to compute. How would you know the upper limit for the Nth prime?

4
5

Is this relevant to this thread?

6

It seems so to me. You asked “How would you know the upper limit for the Nth prime?” From the abstract of this article: “In this paper we establish new upper and lower bounds for the nth prime number p_n”.

Am I misunderstanding you?

7

By the way, a very simple result from the paper is

    p_n < n(log n + 2 log log n)

for all n >= 4.

1 Like
8

As senekor says, sieve is not the only way. For example: given the first m primes, find the (m+1)'th prime.

1 Like
9

I suppose that technically answers my question. However, we don’t expect most students to know that. Most people do not use sieve to figure out the nth prime.

Sieve is also not the most efficient solution and may have pretty poor performance for larger primes.

2 Likes
10

I used the sieve :stuck_out_tongue_winking_eye:

1 Like
11

Hmm, I searched around but couldn’t find any other way to solve nth prime, so I used the Sieve before I even saw that there was also a Sieve problem in the track.

12

I used the highest number from the test cases as my upper limit :innocent:

13

There is a good summary of approaches here: https://stackoverflow.com/questions/9625663/calculating-and-printing-the-nth-prime-number

It identifies a “fast way” that works as follows: compute an approximation a(n) to the nth prime, e.g., using the bounds discussed in the paper that I mentioned above; then compute the actual number of primes <= a(n), i.e., π(a(n)), using an algorithm such as Meissel-Lehmer for π(x); and finally step forward or backward by the delta between n and π(a(n)) using something like trial division.

I haven’t looked into how other students have solved this. I dispute the claim that the sieve “may have pretty poor performance” in the range that we concerns us, though of course I would love to hear about a better approach.

14

If you’re hard coding values from the test into your solution, you’re probably doing it wrong :laughing:

15

TDD, baby!