Recuration Prime Numbers

This is a discussion on Recuration Prime Numbers within the C Programming forums, part of the General Programming Boards category; Hi all, I wrote a code that finding the N'th prime number according to an index that given, for example: ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    27

    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;
    }
    Last edited by megazord; 05-13-2010 at 09:40 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,401
    Use iteration instead of recursion. This particular problem lends itself better to iteration anyway.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Nov 2009
    Posts
    27
    what is the meaning of iteration?

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

  4. #4
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    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. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,401
    Quote Originally Posted by megazord
    what is the meaning of iteration?
    Looping.

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,471
    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
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  7. #7
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    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. #8
    Registered User
    Join Date
    Nov 2009
    Posts
    27
    Quote Originally Posted by vart View Post
    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.

    Quote Originally Posted by vart View Post
    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..

    Quote Originally Posted by Brafil View Post
    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. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,401
    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Nov 2009
    Posts
    27
    Quote Originally Posted by laserlight View Post
    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. #11
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    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. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,401
    Quote 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?

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Registered User
    Join Date
    Nov 2009
    Posts
    27
    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.
    Last edited by megazord; 05-16-2010 at 07:42 AM.

  14. #14
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    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. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,401
    Quote 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?

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Perfect and Prime numbers
    By taggrath in forum C++ Programming
    Replies: 3
    Last Post: 10-22-2009, 02:13 AM
  2. Finding Prime Numbers
    By dan724 in forum C Programming
    Replies: 11
    Last Post: 12-14-2008, 11:12 AM
  3. Checking very large prime numbers
    By password in forum C++ Programming
    Replies: 2
    Last Post: 02-11-2008, 11:26 AM
  4. Replies: 18
    Last Post: 11-04-2005, 01:41 PM
  5. Replies: 2
    Last Post: 09-11-2002, 05:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21