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
cpursley1979Asked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

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.

phoffricCommented:
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
JohnGabyCommented:
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
Ultra_MasterCommented:
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;
}

Open in new window

0
Rowby Goren Makes an Impact on Screen and Online

Learn about longtime user Rowby Goren and his great contributions to the site. We explore his method for posing questions that are likely to yield a solution, and take a look at how his career transformed from a Hollywood writer to a website entrepreneur.

cpursley1979Author 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++;

}

Open in new window

0
phoffricCommented:
cout is for C++. You can use printf instead for C.
0
cpursley1979Author Commented:
could you help write the printf function?
0
Ultra_MasterCommented:
printf("GetPrime(%li) == %l",n,n2);
0
Ultra_MasterCommented:
To be honest your code is a mess.
What are you really trying to do?
0
Ultra_MasterCommented:
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;
}

Open in new window

0
Ultra_MasterCommented:
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;
}

Open in new window

0
cpursley1979Author Commented:
I like it, but it threw up at the bool.  I read C doesn't have bool's.
0
Ultra_MasterCommented:
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;
}

Open in new window

0
cpursley1979Author 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
Ultra_MasterCommented:
Use this instead
#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;
}

Open in new window

0
cpursley1979Author 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;


}

Open in new window

0
phoffricCommented:
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
Ultra_MasterCommented:
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;


}

Open in new window

0
phoffricCommented:
You should declare long GetPrime(long n) before main since you use it in main.
0
phoffricCommented:
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
Ultra_MasterCommented:
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
phoffricCommented:
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
cpursley1979Author Commented:
just one more question how do you insert a new line in
     printf(functioncall "\n")
0
Ultra_MasterCommented:
\n inserts a new line
0
Ultra_MasterCommented:
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

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
cpursley1979Author Commented:
thanks
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Algorithms

From novice to tech pro — start learning today.