programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Liutauras Vilda
• Paul Clapham
• Bear Bibeault
• Jeanne Boyarsky
Sheriffs:
• Ron McLeod
• Tim Cooke
• Devaka Cooray
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Jj Roberts
• Stephan van Hulst
• Carey Brown
Bartenders:
• salvin francis
• Scott Selikoff
• fred rosenberger

Finding the Nth Prime Number

Ranch Hand
Posts: 31
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.

Ranch Hand
Posts: 94
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.

Sheriff
Posts: 11343

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 ]

doburomirushii nikku
Ranch Hand
Posts: 31
Um...I still don't know how to make number go up right...

Here is the code I have now...

marc weber
Sheriff
Posts: 11343
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 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 ]

doburomirushii nikku
Ranch Hand
Posts: 31