Thread: Recuration Prime Numbers

Hi all,

I wrote a code that finding the N'th prime number according to an index that given, for example: "Prime number #7 is 17."

my program working for very small index's, and I need it to work on an index till 1000, but after app. 50 I get "Stuck overFlow"
I need some help to improve my code.
(the int findNthPrime(int n); prototype is a must).

Thanx in advance.

my code:

Code:

#include <stdio.h>
#include <string.h>
#define INPUT_LEN 256

int print_menu(int menu);
int findNthPrime(int n);
int checkingINPUT_LEN(char choise[],int x);
int findingprime(int number,int i,int counter,int j);

void main()
{
	 print_menu(1);
}
int print_menu(int menu)
{
	int  n=0,temp;
	char choice[INPUT_LEN]={0};

	printf("Welcome to Math-N-Stuff.\nPlease select an option from the following menu (1, 2, 3 or 4)."
		   "\n0. Quit.\n1. Finding prime number:\n2. Find all primes on a list of numbers.\n"
		   "3. Calculate mathematical formula.\nPlease enter your choice\n");
	gets(choice);	
	
	switch(choice[0]){
		case '0':
			/*Exit the program*/
			printf("Quitting.\nGoodbye");
			return -1;

		case '1':
			/* Option one, Finding  the Nth prime number,
			   and the smallest prime number bigger then N */

			printf("Please enter parameter:\n");
			scanf("%d",&n);
			//getchar();
			if(n>1000){
				printf("\nParameter too big,\n\n");
				break;
			}
			if(n<1){
				printf("\nIlegal input in option 1\n\n");
				break;
			}
			temp=findNthPrime(n);
			print_menu(1);
			return -1;

		case '2':
			/*Finding all Prime's in arr*/
			print_menu(1);
			return -1;

		case '3':
			/*The function Calculates a formula given in char*/
			print_menu(1);
			return -1;
		
		default:
			/*if the input is wrong*/
			printf("Ilegal input in main menu.\n\n");
			print_menu(1);
			return -1;

	}
	return -1;		
}

int findingprime(int number,int i,int counter,int j)
{
	if(counter==number)
		return --i;
	if(i%j==0){
		i++;
		j=1;}
	if(j>=i/2){
		i++;
		counter++;
		j=1;}
		findingprime(number,i,counter,j+1);
}
int findNthPrime(int n)
{
	int i=2,j=2,counter=1,prime=0;
	prime=findingprime(n,i,counter,j);
	printf("Prime number #%d is %d.\n\n",n,prime);
	return prime;
}

Use iteration instead of recursion. This particular problem lends itself better to iteration anyway.

Originally Posted by megazord

what is the meaning of iteration?

Looping.

Originally Posted by megazord

anyway, the work restriction is to use no loops only recuration.

If you are only allowed to use recursion, then this becomes difficult, if not impossible depending on the circumstances: you have to write the code such that it consumes as little stack space as possible with each recursive call. This may call for the use of global variables so as to avoid function parameters and other variables local to each recursive call - but if a school assignment forces you to resort to poor programming practices, then that school assignment is a poor one. Oh, and in the end, you can still get a stack overflow.

are you ignoring compilation warnings?
something like
" function findingprime - not all paths return a value"?

or you are using compiler that does not produce warnings?

you do not need to go upto i/2 while checking dividers - enogh upto sqrt(i) -
it means the condition could be j*j >= i

another way to decrease number of calls you have to do - store all found prime numbers and check only them as potential dividers

Originally Posted by megazord

I google it for days, not even a clue :\

The sieve of Eratosthenes could be appropriate (the 1000th prime is 7919, if I remember correctly), but it is a matter of how you write the recursive function so as to delay stack overflow for as long as possible.

Originally Posted by megazord

I read about it friday, i saw that what vast offer me is close to that implantaion (sqrt i).
I tried to make a funcation that ignor from wall the multiplaies of 2,3,5,7 etc..
but no success, recurcvily matter.

What did you try?

Originally Posted by Brafil

Store all primes in an array, starting from two, then for each number check if it's divisable through an of these numbers, if it isn't, then it is a prime.

That does not make sense though: if the rules allow one to store "all" primes in an array, then you need neither iteration nor recursion: for any valid input n, print primes[n-1] and you're done.

I tried to make some If's there

if (i%2==0)
findingprime(number,i,counter,j+1);

if(i%3==0)
findingprime(number,i,counter,j+1);

etc.. till 24 (I have sense why 24 but i forgot what was it).

I think need less If and to return the recursion back all the time some how for less use of the recursion.

Originally Posted by Brafil

The user could do this and calculate more primes on demand with this technique.

Yes, that is the basis for my (invalid) submission for a primality testing contest here. Yet, with just 1000 primes, it is feasible to hard code all of them, instead of using a hard coded base of the first 24 primes to generate them all. But megazord, do the rules allow such hard coding in the first place?

Originally Posted by Brafil

I think you could loop over all numbers till 1000 and then check for each number if it's a prime with a recursive is_prime() function.

Incidentally, that is inaccurate: the aim is to find the nth prime, with n in the range [1, 1000]. Checking natural numbers no greater than 1000 would not find all such primes. A check shows that my memory did not fail me: 7919 is the 1000th prime, hence one would need to check to 7919.