943,496 Members | Top Members by Rank

Software Development > C > Recursive prime number f(x)
Ad:
  • C Discussion Thread
  • Unsolved
  • Views: 25387
  • C RSS
You are currently viewing page 1 of this multi-page discussion thread
Permalink
Jun 21st, 2004
1

Recursive prime number f(x)

Expand Post »
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...
  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
Similar Threads
Reputation Points: 113
Solved Threads: 3
Posting Whiz
Asif_NSU is offline Offline
353 posts
since Apr 2004
Permalink
Jun 21st, 2004
2

Re: Recursive prime number f(x)

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".
Reputation Points: 36
Solved Threads: 11
Posting Pro in Training
Chainsaw is offline Offline
436 posts
since Jun 2004
Permalink
Jun 21st, 2004
0

Re: Recursive prime number f(x)

Quote 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.
Reputation Points: 115
Solved Threads: 5
Junior Poster
Toba is offline Offline
192 posts
since Jun 2004
Permalink
Jun 24th, 2004
2

Re: Recursive prime number f(x)

Quote ...
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? 
  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. }

Quote 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.
K-1
Reputation Points: 12
Solved Threads: 0
Newbie Poster
K-1 is offline Offline
6 posts
since Jun 2004
Permalink
Jun 24th, 2004
1

Re: Recursive prime number f(x)

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:

  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.
Reputation Points: 115
Solved Threads: 5
Junior Poster
Toba is offline Offline
192 posts
since Jun 2004
Permalink
Jun 24th, 2004
0

Re: Recursive prime number f(x)

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
  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: 
  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
Reputation Points: 113
Solved Threads: 3
Posting Whiz
Asif_NSU is offline Offline
353 posts
since Apr 2004
Permalink
Jun 24th, 2004
0

Re: Recursive prime number f(x)

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? 
  1. int is_prime(int n,int p)//is p of any use?
  2. {
  3. return is_prime_helper(n,n-1);
  4. }
Reputation Points: 113
Solved Threads: 3
Posting Whiz
Asif_NSU is offline Offline
353 posts
since Apr 2004
Permalink
Jun 24th, 2004
0

Re: Recursive prime number f(x)

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. 
  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. }
Reputation Points: 113
Solved Threads: 3
Posting Whiz
Asif_NSU is offline Offline
353 posts
since Apr 2004
Permalink
Jun 24th, 2004
0

Re: Recursive prime number f(x)

Ah, i see where I made that mistake. That's what you get for doing recursion at 3am
K-1
Reputation Points: 12
Solved Threads: 0
Newbie Poster
K-1 is offline Offline
6 posts
since Jun 2004
Permalink
Jun 25th, 2004
0

Re: Recursive prime number f(x)

Quote 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? 
  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.
Reputation Points: 36
Solved Threads: 11
Posting Pro in Training
Chainsaw is offline Offline
436 posts
since Jun 2004

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C Forum Timeline: program help
Next Thread in C Forum Timeline: Assign content to a function pointer





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC