# Thread: Recuration Prime Numbers

1. ## 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).

my code:

Code:
```#include <stdio.h>
#include <string.h>
#define INPUT_LEN 256

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

void main()
{
}
{
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 */

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);
return -1;

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

case '3':
/*The function Calculates a formula given in char*/
return -1;

default:
/*if the input is wrong*/
printf("Ilegal input in main menu.\n\n");
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;
}```

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

3. what is the meaning of iteration?

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

4. If you have to use recursion, then you'll have to be smart about the way you do it. Keep in mind that for EACH time you call a function, the ENTIRE FUNCTION gets pushed to the stack. The stack is limited by physical memory (and often by the size dictated by the OS per program) so there is no way around it. What one COULD do, however, is to set MIN and MAX values to "loop" through in your stack. This way you'd be consuming only part of the stack while limiting your number of concurrent functions on the stack to like 10 -- which would be MUCH better than say 100.

5. 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.

6. 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

7. You can use a different algorithm for that, there are plenty on the web.

BTW, your compiler should support tail-recursion-elimination. If it doesn't, go use Scheme.

8. Originally Posted by vart
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?
I'm searching a "return" for that, not yet founded.

Originally Posted by vart
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
I use that advise! thnx, it wat helpfull but, I still donwt get to 1000, get only 623.
I think I need another "if" there. i don't know which..

Originally Posted by Brafil
You can use a different algorithm for that, there are plenty on the web.
BTW, your compiler should support tail-recursion-elimination. If it doesn't, go use Scheme.
I google it for days, not even a clue :\

9. 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.

10. Originally Posted by laserlight
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.
yes, thank you.
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.

11. 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.

12. 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.

13. 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.

14. 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.
The user could do this and calculate more primes on demand with this technique.

Both solutions (this one and the one above) would not be recursive. 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. That would use less stack space depending on the implementation.

15. 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.

Popular pages Recent additions