# Write a function that returns the nth prime number

Write a function that returns the nth prime number corresponding to the number n passed.
// •    Do not worry about overflow.  Assume that a long will hold all required values.
// •    Optimize for readability and compactness, not speed.
// •    Do not use any complex math formulas to calculate it.
// •    Do not use any math operators beyond addition, subtraction, multiplication, division.//
// Examples:
// GetPrime(1) == 2 // the first prime number is 2
// GetPrime(2) == 3 // the second prime number is 3
// GetPrime(3) == 5 // the third prime number is 5
// GetPrime(4) == 7 // the fourth prime number is 7
// GetPrime(5) == 11 // the fifth prime number is 11
// GetPrime(1000) == 7909 // the thousandth prime number is 7909
###### Who is Participating?

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
This question is academic in nature. Assuming that you are self-studying, how about showing an attempt and then ask a question if you get stuck on something.

Here is a link showing pseudo-code to determine if a number is prime:
http://www.java2s.com/Code/CSharp/Language-Basics/DetermineifanumberisprimeIfitisnotthendisplayitslargestfactor.htm

(pseudo, because it's in C#)
0
Commented:
I you are looking for an efficient method of computing prime numbers you might want to look at the Sieve of Eratosthenes:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
0
Commented:
Hi,

The code below represents such a function.
By the way 7909 is not a prime number as it is divisible by 11, thereby GetPrime(1000) = 7919.

Good luck learning C,
Ultra_Master
``````int GetPrime(int val){
int counter=0, number=1, index;
bool isPrime;

while (counter!=val){
++number;
isPrime = true;
for (index = 2 ; index <= number/2; index++)
if (number % index == 0 ) {
isPrime = false;
break;
}
if (isPrime) counter++;
}
return number;
}
``````
0
Author Commented:
I compiled the code below but I think it has some errors:
\$ gcc -Wall dmp.c
dmp.c: In function `main':
dmp.c:34: error: parse error before "long"
dmp.c:36: error: `cout' undeclared (first use in this function)
dmp.c:36: error: (Each undeclared identifier is reported only once
dmp.c:36: error: for each function it appears in.)
dmp.c:36: error: `endl' undeclared (first use in this function)
dmp.c: In function `GetPrime':
dmp.c:90: error: 'for' loop initial declaration used outside C99 mode
dmp.c:92: error: 'for' loop initial declaration used outside C99 mode
dmp.c:99: error: parse error at end of input
``````#include <stdio.h>
#include <string.h>

long GetPrime(long n);

int main (int argc, char * argv[])
{

//GetPrime function
long n = 0;
if(n<=0)
{return 1;}
else
long n2 = GetPrime(n);

cout << "GetPrime(" << n << ") == " << n2 << endl;

return 0;
}

long GetPrime(long n)
{
int temp = 2;
for (int counter=1; counter<=n; counter++){
counter ++;
for (int divisor=2; divisor <= temp; divisor++){
if (divisor % temp ==0){
break;
}
}
temp++;

}
``````
0
Commented:
cout is for C++. You can use printf instead for C.
0
Author Commented:
could you help write the printf function?
0
Commented:
printf("GetPrime(%li) == %l",n,n2);
0
Commented:
0
Commented:
To be honest your code is a mess.
What are you really trying to do?
0
Commented:
For example, this program reads a number "n" and generates and displays the first "n" prime numbers.
``````#include <stdio.h>

int GetPrime(int val){
int counter=0, number=1, index;
bool isPrime;

while (counter!=val){
++number;
isPrime = true;
for (index = 2 ; index <= number/2; index++)
if (number % index == 0 ) {
isPrime = false;
break;
}
if (isPrime) counter++;
}
return number;
}

int _tmain(int argc, _TCHAR* argv[])
{
int n,result;
printf("n=");scanf("%d",&n);
printf("\nShow the first %d prime numbers:\n",n);

for (int i=1; i<=n; i++){
result = GetPrime(i);
printf("\n Prime no. %d is: %d \n",i,result);
}

return 0;
}
``````
0
Commented:
This is a simpler version that should work under Linux:
``````#include <stdio.h>

int GetPrime(int val){
int counter=0, number=1, index;
bool isPrime;

while (counter!=val){
++number;
isPrime = true;
for (index = 2 ; index <= number/2; index++)
if (number % index == 0 ) {
isPrime = false;
break;
}
if (isPrime) counter++;
}
return number;
}

int main()
{
int n,result,i;
printf("n=");scanf("%d",&n);
printf("\nShow the first %d prime numbers:\n",n);

for (i=1; i<=n; i++){
result = GetPrime(i);
printf("\n Prime no. %d is: %d \n",i,result);
}

return 0;
}
``````
0
Author Commented:
I like it, but it threw up at the bool.  I read C doesn't have bool's.
0
Commented:
No more booleans :)
``````#include <stdio.h>

int GetPrime(int val){
int counter=0, number=1, index;
int isPrime;

while (counter!=val){
++number;
isPrime = 1;
for (index = 2 ; index <= number/2; index++)
if (number % index == 0 ) {
isPrime = 0;
break;
}
if (isPrime) counter++;
}
return number;
}

int main()
{
int n,result;
printf("n=");scanf("%d",&n);
printf("\nShow the first %d prime numbers:\n",n);

for (int i=1; i<=n; i++){
result = GetPrime(i);
printf("\n Prime no. %d is: %d \n",i,result);
}

return 0;
}
``````
0
Author Commented:
I keep getting these errors:
\$ gcc -Wall dmp.c
dmp.c: In function `main':
dmp.c:31: warning: int format, long int arg (arg 2)
dmp.c:31: warning: int format, long int arg (arg 2)
dmp.c:32: warning: int format, long int arg (arg 2)
dmp.c:32: warning: int format, long int arg (arg 2)
dmp.c:34: error: 'for' loop initial declaration used outside C99 mode
dmp.c:36: warning: int format, long int arg (arg 2)
dmp.c:36: warning: int format, long int arg (arg 3)
dmp.c:36: warning: int format, long int arg (arg 2)
dmp.c:36: warning: int format, long int arg (arg 3)
0
Commented:
``````#include <stdio.h>

int GetPrime(int val){
int counter=0, number=1, index;
int isPrime;

while (counter!=val){
++number;
isPrime = 1;
for (index = 2 ; index <= number/2; index++)
if (number % index == 0 ) {
isPrime = 0;
break;
}
if (isPrime) counter++;
}
return number;
}

int main()
{
int n,result,i;
printf("n=");scanf("%d",&n);
printf("\nShow the first %d prime numbers:\n",n);

for (i=1; i<=n; i++){
result = GetPrime(i);
printf("\n Prime no. %d is: %d \n",i,result);
}

return 0;
}
``````
0
Author Commented:
\$ gcc -Wall dmp.c
dmp.c: In function `main':
dmp.c:31: warning: int format, long int arg (arg 2)
dmp.c:31: warning: int format, long int arg (arg 2)
dmp.c:32: warning: int format, long int arg (arg 2)
dmp.c:32: warning: int format, long int arg (arg 2)
dmp.c:34: error: 'for' loop initial declaration used outside C99 mode
dmp.c:36: warning: int format, long int arg (arg 2)
dmp.c:36: warning: int format, long int arg (arg 3)
dmp.c:36: warning: int format, long int arg (arg 2)
dmp.c:36: warning: int format, long int arg (arg 3)
``````#include <stdio.h>
int main (int argc, char * argv[])
{
//GetPrime function
long n,result;
printf("n=");scanf("%d",&n);
printf("\nShow the first %d prime numbers:\n",n);

for (long i=1; i<=n; i++){
result = GetPrime(i);
printf("\n Prime no. %d is: %d \n",i,result);
}

return 0;
}

long GetPrime(long n)
{
long counter=0, number=1, index;
long isPrime;

while (counter!=n){
++number;
isPrime = 1;
for (index = 2 ; index <= number/2; index++){
if (number % index == 0 ) {
isPrime = 0;
break;
}
if (isPrime) counter++;
}
}
return number;

}
``````
0
Commented:
To remove the error change
for (long i=1; i<=n; i++){
to
for (i=1; i<=n; i++){
and declare
long i;
at top of function.
0
Commented:
In main declare the variable i not in the for but together with n and result
``````#include <stdio.h>
int main (int argc, char * argv[])
{
//GetPrime function
long n,result, i;
printf("n=");scanf("%d",&n);
printf("\nShow the first %d prime numbers:\n",n);

for (i=1; i<=n; i++){
result = GetPrime(i);
printf("\n Prime no. %d is: %d \n",i,result);
}

return 0;
}

long GetPrime(long n)
{
long counter=0, number=1, index;
long isPrime;

while (counter!=n){
++number;
isPrime = 1;
for (index = 2 ; index <= number/2; index++){
if (number % index == 0 ) {
isPrime = 0;
break;
}
if (isPrime) counter++;
}
}
return number;

}
``````
0
Commented:
You should declare long GetPrime(long n) before main since you use it in main.
0
Commented:
To get rid of warnings such as:
dmp.c:31: warning: int format, long int arg (arg 2)

change the %d to %ld to indicate that there is a long variable being converted.
0
Commented:
The warnings pose no problem at all. Linux yells more about these little things. For an academic example it doesn't matter so much. This is about the algorithm if I understood right.
As for the wrong declaration, it works under Windows, so I've changed it in my last code snippets but it seems it went  unnoticed by the author :)

Cheers,
Ultra_Master
0
Commented:
For a professional, it is better to remove all warnings, since some warnings are not so benign. Having a slew of benign warnings easily can hide a serious warning. So in industry, you want to eliminate warnings so that when a serious one pops up, it immediately gets your attention.

If this is academic question, then we are not supposed to provide solutions as Ultra_Master should know.

If you want to reduce the number of warnings, you can remove the -Wall and only more serious warnings will show up.
0
Author Commented:
just one more question how do you insert a new line in
printf(functioncall "\n")
0
Commented:
\n inserts a new line
0
Commented:
printf( "\n\n\n%d",function_call()); inserts 3 new lines and displays an integer returned by the fucntion_call() function
0

Experts Exchange Solution brought to you by