# Finding the Nth Prime Number

doburomirushii nikku

Ranch Hand

Posts: 31

posted 10 years ago

Hello,

I have to make a program that finds the nth prime number. Basically, the user types in a number, for example, 10 and the program outputs 29 (the 10th prime number).

I have created my program and I think I must be on the right track since when I input 10 the program outputs 28. The actual output is always a few numbers off the expected output and as you go higher...say you input 12, the program will output 32 as opposed to 37.

I think it is something to do with the way I increment my "number" value and I have played with it to make it go through the numbers as I want but have had no luck.

I have to make a program that finds the nth prime number. Basically, the user types in a number, for example, 10 and the program outputs 29 (the 10th prime number).

I have created my program and I think I must be on the right track since when I input 10 the program outputs 28. The actual output is always a few numbers off the expected output and as you go higher...say you input 12, the program will output 32 as opposed to 37.

I think it is something to do with the way I increment my "number" value and I have played with it to make it go through the numbers as I want but have had no luck.

Robert Hill

Ranch Hand

Posts: 94

posted 10 years ago

Generally speaking the number 1 is not a prime number. The first prime number is 2 so you started there. After 2 there are no prime numbers that are even, so only odd numbers fill the remaining set of primes. So start at 3 for the second prime, check it for primeness, then increment by 2. Rinse and repeat, until you have found n primes.

A quick way to check for primes, is to take the square root of the number in question and check all the integral values up to that square. ie square root of 37 oe 6.xxx so use 6.

In your case, you will know that any number you check is odd, so it is not divisible by 2, thus can start at 3, using modulus, and then increment the value until it is > the square root of n. There are lots of details hidden in this, but hopefully will get you on track.

A quick way to check for primes, is to take the square root of the number in question and check all the integral values up to that square. ie square root of 37 oe 6.xxx so use 6.

In your case, you will know that any number you check is odd, so it is not divisible by 2, thus can start at 3, using modulus, and then increment the value until it is > the square root of n. There are lots of details hidden in this, but hopefully will get you on track.

posted 10 years ago

The number 1 is definitely not prime. This is by definition, to ensure that each composite has a unique prime factorization (in accordance with the fundamental theorem of arithmetic).

[ February 24, 2006: Message edited by: marc weber ]

Originally posted by Robert Hill:

Generally speaking the number 1 is not a prime number...

The number 1 is definitely not prime. This is by definition, to ensure that each composite has a unique prime factorization (in accordance with the fundamental theorem of arithmetic).

[ February 24, 2006: Message edited by: marc weber ]

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." *~Joe Strummer*

sscce.org

doburomirushii nikku

Ranch Hand

Posts: 31

posted 10 years ago

To clarify the logic, I suggest carefully describing your process in English (actually write it out, in complete sentences!), and then translate that to code. For example, working from what you have, you might say...

I already know that 2 and 3 are both prime, so I'm starting at prime = 2 (because I have identified the first 2 primes) and number = 3 (because that's the last number I tested). I need to continue testing until prime == nthprime.

So far so good. Now, inside this loop, I want to test the next number. Because I only need to test odds, I can increment number by 2. To test number, I want to check ints from 3 to sqrt(number) and see if they are proper factors of number. (Hmmm... I

Hmmm... Already, this looks different, because number is being incremented

And come to think of it, when I'm going from 3 to square, do I need to test square too? That is, should my for loop use "less than or equal to"? Or is it okay with just "less than"?

Try continuing along this path, and see where it gets you.

[ February 25, 2006: Message edited by: marc weber ]

I already know that 2 and 3 are both prime, so I'm starting at prime = 2 (because I have identified the first 2 primes) and number = 3 (because that's the last number I tested). I need to continue testing until prime == nthprime.

So far so good. Now, inside this loop, I want to test the next number. Because I only need to test odds, I can increment number by 2. To test number, I want to check ints from 3 to sqrt(number) and see if they are proper factors of number. (Hmmm... I

*could*put Math.sqrt(number) in the boolean test of the for loop, but then it will calculate the same square root*every iteration.*That doesn't seem efficient, so maybe I'll just calculate it*once*instead and call it "square.")Hmmm... Already, this looks different, because number is being incremented

*outside*of the testing loop.And come to think of it, when I'm going from 3 to square, do I need to test square too? That is, should my for loop use "less than or equal to"? Or is it okay with just "less than"?

Try continuing along this path, and see where it gets you.

[ February 25, 2006: Message edited by: marc weber ]

*~Joe Strummer*

sscce.org

doburomirushii nikku

Ranch Hand

Posts: 31

posted 10 years ago

I got it to work using your advice.

Talked it through and realized that since the square root of 9 was three it would skip the for loop and denote it as prime. Then I realized like you hinted at, that the for loop had to be inclusive.

Thanks for all the help everyone. The best part is that I really understand how to do this problem now!

Talked it through and realized that since the square root of 9 was three it would skip the for loop and denote it as prime. Then I realized like you hinted at, that the for loop had to be inclusive.

Thanks for all the help everyone. The best part is that I really understand how to do this problem now!

It is sorta covered in the JavaRanch Style Guide. |