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?
 
Ultra_MasterConnect With a Mentor Commented:
printf( "\n\n\n%d",function_call()); inserts 3 new lines and displays an integer returned by the fucntion_call() function
0
 
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
Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
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
 
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
 
cpursley1979Author Commented:
thanks
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.