•
•
•
•
What is DaniWeb IT Discussion Community?
You're currently browsing the C section within the Software Development category of DaniWeb, a massive community of 456,417 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 2,606 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.
Please support our C advertiser: Programming Forums
Views: 11695 | Replies: 12
 |
•
•
Join Date: Apr 2004
Location: Dhaka, Bangladesh
Posts: 344
Reputation: 
Rep Power: 5
Solved Threads: 3
Posting Whiz
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...
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?
#include<stdio.h>
#include<conio.h>
#include<assert.h>
int is_prime(int n);
void main(void)
{
int n=0;
clrscr();
printf("An integer ");
scanf("%d",&n);
assert(n > 1);
n=is_prime(n);
if (n==1)
printf("\nThe number is prime");
else
printf("\nThe number is NOT a prime");
getch();
}
int is_prime(int n)
{
int i;
for(i=2;i<n;i++){
if (n%i) continue;
else return 0;
}
return 1;
}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
•
•
Join Date: Jun 2004
Location: Marin, CA, USA
Posts: 434
Reputation:
Rep Power: 5
Solved Threads: 10
Unprevaricator
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".
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".
•
•
Join Date: Jun 2004
Location: Worcester, Massachusetts
Posts: 180
Reputation:
Rep Power: 5
Solved Threads: 3
Junior Poster
•
•
•
•
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.
•
•
Join Date: Jun 2004
Posts: 6
Reputation:
Rep Power: 0
Solved Threads: 0
Newbie Poster
•
•
•
•
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?
#include<stdio.h>
#include<conio.h>
#include<assert.h>
int is_prime(int n);
void main(void)
{
int n=0;
clrscr();
printf("An integer ");
scanf("%d",&n);
assert(n > 1);
n=is_prime(n, 2);
if (n==1)
printf("\nThe number is prime");
else
printf("\nThe number is NOT a prime");
getch();
}
int is_prime(int n, int z)
{
if((n%z)==0)
return 1;
else
{
if(z<n)
return is_prime(n,z+1);
else
return 0;
}
}•
•
•
•
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.
•
•
Join Date: Jun 2004
Location: Worcester, Massachusetts
Posts: 180
Reputation:
Rep Power: 5
Solved Threads: 3
Junior Poster
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:
This code is untested, but it will work.
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:
Dim n as Integer
Dim test as Integer
Dim isPrime as Boolean
n = val(inputbox("Number to check:")
isPrime = false
For test = 2 to int(sqr(n))
If n mod test = 0 Then
isPrime = true
Exit For
End If
Next test
If isPrime Then
MsgBox "Number is prime"
Else
MsgBox "Number is divisible by " & test
End IfThis code is untested, but it will work.
what? WHAT?
•
•
Join Date: Apr 2004
Location: Dhaka, Bangladesh
Posts: 344
Reputation:
Rep Power: 5
Solved Threads: 3
Posting Whiz
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
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:
I found that there were a few problems with your code. It returns everything as a prime.
I tried changing ur code to this
int is_prime(int n, int z)
{
if((n%z)==0)
return 0;//should be 0
else
{
if(z<n)
return is_prime(n,z+1);
else
return 1;//should be one
}
}
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:
int is_prime(int n, int z)
{
if(n==z) return 1;
else if((n%z)==0)
return 0;
else if(z<n)
return is_prime(n,z+1);
} Last edited by Asif_NSU : Jun 24th, 2004 at 5:59 am. Reason: typo
•
•
Join Date: Apr 2004
Location: Dhaka, Bangladesh
Posts: 344
Reputation:
Rep Power: 5
Solved Threads: 3
Posting Whiz
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?
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?
int is_prime(int n,int p)//is p of any use?
{
return is_prime_helper(n,n-1);
} •
•
Join Date: Apr 2004
Location: Dhaka, Bangladesh
Posts: 344
Reputation:
Rep Power: 5
Solved Threads: 3
Posting Whiz
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.
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.
#include<stdio.h>
#include<conio.h>
#include<assert.h>
#include<math.h>
int is_prime(int n)
{
int test;
for(test =2; test <=(int)sqrt(n); test++){
if (n%test!=0)
continue;
else
return 0;
}
return 1;
}
void main(void)
{
int n=0;
clrscr();
printf("An integer ");
scanf("%d",&n);
assert(n > 1);
n=is_prime(n);
if (n==1)
printf("\nThe number is prime");
else
printf("\nThe number is NOT a prime");
getch();
} •
•
Join Date: Jun 2004
Posts: 6
Reputation:
Rep Power: 0
Solved Threads: 0
Newbie Poster
Ah, i see where I made that mistake. That's what you get for doing recursion at 3am 
•
•
Join Date: Jun 2004
Location: Marin, CA, USA
Posts: 434
Reputation:
Rep Power: 5
Solved Threads: 10
Unprevaricator
•
•
•
•
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?int is_prime(int n,int p)//is p of any use? { return is_prime_helper(n,n-1); }
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.
|
•
•
•
•
•
•
•
•
DaniWeb C Marketplace
•
•
•
•
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
Linear Mode
Similar Threads
Other Threads in the C Forum
- Previous Thread: program help
- Next Thread: Assign content to a function pointer
