Recursive prime number f(x)

Please support our C advertiser: Programming Forums - DaniWeb Sister Site
Reply
1 2

•
•
Join Date: Apr 2004
Posts: 353
Reputation: Asif_NSU is on a distinguished road 
Solved Threads: 2
Asif_NSU's Avatar
Asif_NSU Asif_NSU is offline Offline
Posting Whiz

Recursive prime number f(x)

 
1
  #1
Jun 21st, 2004
I wrote this code that checks whether a number is prime or not. It returns 1 if the number is prime or 0 otherwise. U just look at the bottom of the code...
C Syntax (Toggle Plain Text) 
  1. #include<stdio.h>
  2. #include<conio.h>
  3. #include<assert.h>
  4.  
  5. int is_prime(int n);
  6.  
  7. void main(void)
  8. {
  9. 	int n=0;
  10. 	clrscr();
  11. 	printf("An integer ");
  12. 	scanf("%d",&n);
  13. 	assert(n > 1);
  14. 	n=is_prime(n);
  15. 	if (n==1)
  16. 		printf("\nThe number is prime");
  17. 	else
  18. 		printf("\nThe number is NOT a prime");
  19. 	getch();
  20. }
  21.  
  22. int is_prime(int n)
  23. {
  24. 	int i;
  25. 	for(i=2;i<n;i++){
  26. 	      if (n%i)	 continue;
  27. 	      else	 return 0;
  28. 	}
  29. 	return 1;
  30. }

But againnnnn... i want to know how can i convert the iterative version into a recursive one. Will anyone help me convert this prime checking function into a recursive one?
Last edited by Asif_NSU; Jun 21st, 2004 at 11:18 am. Reason: none
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2004
Posts: 436
Reputation: Chainsaw is an unknown quantity at this point 
Solved Threads: 10
Chainsaw's Avatar
Chainsaw Chainsaw is offline Offline
Unprevaricator

Re: Recursive prime number f(x)

 
2
  #2
Jun 21st, 2004
How about:

int is_prime_helper( int n, int test )
{
if (test < 2) return 1;
if (!(n%test)) return 0;
return is_prime_helper(n,test-1);
}

int is_prime(int n,int p)
{
return is_prime_helper(n,n-1);
}

This is using your existing code as a template for the algorithm. There are better ways of finding tests for primes, though. For example, if you are looking for 123 to see if it is prime, anything more than HALF 123 can't divide into it evenly. so no point checking those. Another thing to realize is that if it isn't divisible by 2 it isn't divisible by ANY even number, so maybe check for 2, then all odd numbers. Gee, but if it isn't divisible by 3 it isn't divisible by 9 or any other multiple of 3. And so on. For the real key to minimal checks, look in Google for "Sieve of Eratosthenes".
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2004
Posts: 192
Reputation: Toba is an unknown quantity at this point 
Solved Threads: 5
Toba's Avatar
Toba Toba is offline Offline
Junior Poster

Re: Recursive prime number f(x)

 
0
  #3
Jun 21st, 2004
•
•
•
•
Originally Posted by Chainsaw
anything more than HALF 123 can't divide into it evenly
Actually, you only have to go up to the square root of the number. If the number is a square, you'll get it, and if it isn't, you'll get one factor of each possible set, which is enough.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2004
Posts: 6
Reputation: K-1 is an unknown quantity at this point 
Solved Threads: 0
K-1's Avatar
K-1 K-1 is offline Offline
Newbie Poster

Re: Recursive prime number f(x)

 
2
  #4
Jun 24th, 2004
•
•
•
•
But againnnnn... i want to know how can i convert the iterative version into a recursive one. Will anyone help me convert this prime checking function into a recursive one?
C Syntax (Toggle Plain Text) 
  1. #include<stdio.h>
  2. #include<conio.h>
  3. #include<assert.h>
  4.  
  5. int is_prime(int n);
  6.  
  7. void main(void)
  8. {
  9. 	int n=0;
  10. 	clrscr();
  11. 	printf("An integer ");
  12. 	scanf("%d",&n);
  13. 	assert(n > 1);
  14. 	n=is_prime(n, 2);
  15. 	if (n==1)
  16. 		printf("\nThe number is prime");
  17. 	else
  18. 		printf("\nThe number is NOT a prime");
  19. 	getch();
  20. }
  21.  
  22. int is_prime(int n, int z)
  23. {
  24.              if((n%z)==0)
  25.                      return 1;
  26.              else
  27.              {
  28.                      if(z<n)
  29.                             return is_prime(n,z+1);
  30.                      else
  31.                             return 0;
  32.              }
  33. }

•
•
•
•
Originally Posted by Toba
Actually, you only have to go up to the square root of the number. If the number is a square, you'll get it, and if it isn't, you'll get one factor of each possible set, which is enough.
That's only if your trying to find all the primes up to a certain number, you filter out all multiples of the primes up to that numbers square root, all numbers left are prime.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2004
Posts: 192
Reputation: Toba is an unknown quantity at this point 
Solved Threads: 5
Toba's Avatar
Toba Toba is offline Offline
Junior Poster

Re: Recursive prime number f(x)

 
1
  #5
Jun 24th, 2004
Nice code.

However, on low-memory systems, this smells like a stack crash (very recursive).

BTW, even if you are just checking for divisibility (ie. num1 % num2 == 0) to determine if a specific number is prime, you only need to check for divisibility up to the square root. Here's a quick snippet of VB code to do this:

C Syntax (Toggle Plain Text) 
  1. Dim n as Integer
  2. Dim test as Integer
  3. Dim isPrime as Boolean
  4.  
  5. n = val(inputbox("Number to check:")
  6. isPrime = false
  7.  
  8. For test = 2 to int(sqr(n))
  9.     If n mod test = 0 Then
  10.         isPrime = true
  11.         Exit For
  12.     End If
  13. Next test
  14.  
  15. If isPrime Then
  16.     MsgBox "Number is prime"
  17. Else
  18.     MsgBox "Number is divisible by " & test
  19. End If

This code is untested, but it will work.
what? WHAT?
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2004
Posts: 353
Reputation: Asif_NSU is on a distinguished road 
Solved Threads: 2
Asif_NSU's Avatar
Asif_NSU Asif_NSU is offline Offline
Posting Whiz

Re: Recursive prime number f(x)

 
0
  #6
Jun 24th, 2004
To k-1:
I found that there were a few problems with your code. It returns everything as a prime.
I tried changing ur code to this
C Syntax (Toggle Plain Text) 
  1. int is_prime(int n, int z)
  2. {
  3.              if((n%z)==0)
  4.                      return 0;//should be 0
  5.              else
  6.              {
  7.                      if(z<n)
  8.                             return is_prime(n,z+1);
  9.                      else
  10.                             return 1;//should be one
  11.              }
  12. }

I did so , bcos in MY code i actully printed "The number is prime" when the value returned by the func was 1(true); But still it didnt help. For the moment it merely printed "the number is NOT prime" for all cases.

Therefore, the problem that i found was actually in base case of the recursive function. z gets incremented to n and eventually n%n yields to 0; So i just added one more line in the beginning of the function:
C Syntax (Toggle Plain Text) 
  1. int is_prime(int n, int z)
  2. {
  3. 	     if(n==z) return 1;
  4.  
  5. 	     else if((n%z)==0)
  6. 		     return 0;
  7.  
  8. 	     else if(z<n)
  9. 		      return is_prime(n,z+1);
  10.  
  11. }
Last edited by Asif_NSU; Jun 24th, 2004 at 5:59 am. Reason: typo
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2004
Posts: 353
Reputation: Asif_NSU is on a distinguished road 
Solved Threads: 2
Asif_NSU's Avatar
Asif_NSU Asif_NSU is offline Offline
Posting Whiz

Re: Recursive prime number f(x)

 
0
  #7
Jun 24th, 2004
To Chainsaw:
Thanx, ur code works just fine, but why did u pass two parameters in the is_prime() function. I mean we dont actually need int p, do we?
C Syntax (Toggle Plain Text) 
  1. int is_prime(int n,int p)//is p of any use?
  2. {
  3. return is_prime_helper(n,n-1);
  4. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2004
Posts: 353
Reputation: Asif_NSU is on a distinguished road 
Solved Threads: 2
Asif_NSU's Avatar
Asif_NSU Asif_NSU is offline Offline
Posting Whiz

Re: Recursive prime number f(x)

 
0
  #8
Jun 24th, 2004
To Toba:
I think u r right. We only need check upto the squre root of the function.
I converted ur VB code into C code, i checked it and it works fine.
Thanx.
C Syntax (Toggle Plain Text) 
  1. #include<stdio.h>
  2. #include<conio.h>
  3. #include<assert.h>
  4. #include<math.h>
  5.  
  6. int is_prime(int n)
  7. {
  8. 	int test;
  9. 	for(test =2; test <=(int)sqrt(n); test++){
  10. 		if (n%test!=0)
  11. 			continue;
  12. 		else
  13. 			return 0;
  14.       }
  15.       return 1;
  16.  
  17. }
  18.  
  19. void main(void)
  20. {
  21. 	int n=0;
  22. 	clrscr();
  23. 	printf("An integer ");
  24. 	scanf("%d",&n);
  25. 	assert(n > 1);
  26. 	n=is_prime(n);
  27. 	if (n==1)
  28. 		printf("\nThe number is prime");
  29. 	else
  30. 		printf("\nThe number is NOT a prime");
  31. 	getch();
  32. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2004
Posts: 6
Reputation: K-1 is an unknown quantity at this point 
Solved Threads: 0
K-1's Avatar
K-1 K-1 is offline Offline
Newbie Poster

Re: Recursive prime number f(x)

 
0
  #9
Jun 24th, 2004
Ah, i see where I made that mistake. That's what you get for doing recursion at 3am
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2004
Posts: 436
Reputation: Chainsaw is an unknown quantity at this point 
Solved Threads: 10
Chainsaw's Avatar
Chainsaw Chainsaw is offline Offline
Unprevaricator

Re: Recursive prime number f(x)

 
0
  #10
Jun 25th, 2004
•
•
•
•
Originally Posted by Asif_NSU
To Chainsaw:
Thanx, ur code works just fine, but why did u pass two parameters in the is_prime() function. I mean we dont actually need int p, do we?
C Syntax (Toggle Plain Text) 
  1. int is_prime(int n,int p)//is p of any use?
  2. {
  3. return is_prime_helper(n,n-1);
  4. }
Ha ha ha, thats what I get for writing code in notepad.

How about this (incorporating your fix and the sqrt thingy):

int is_prime(int n)
{
return is_prime_helper(n,(int)sqrt(n));
}

note the cast of the double returned by sqrt into an int. There was a time when sqrt was very costly (on non-floating point machines). Not sure that matters anymore.
Reply With Quote Quick reply to this message  
Reply
1 2

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C Forum


Views: 15810 | Replies: 12
Thread Tools Search this Thread



Tag cloud for C
#include * .net append array arrays asterisks binarysearch calculate changingto char character cm command copyimagefile cprogramme creafecopyofanytypeoffileinc database directory dynamic execv feet fgets file fork forloop framework function functions givemetehcodez grade graphics gtkwinlinux hacking histogram homework include incrementoperators input intmain() iso kernel keyboard km lazy license linked linkedlist linux list lists locate logical_drives looping loopinsideloop. lowest matrix microsoft mqqueue mysql number oddnumber odf opensource overwrite owf pdf performance pointer pointers posix probleminc process program programming radix recursion recv recvblocked research reversing scanf scripting segmentationfault sequential socket spoonfeeding standard string student systemcall testing threads turboc unix user variable wab whythiscodecausesegmentationfault windowsapi
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC