Recursive prime number f(x)

[Asif_NSU]

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

#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?

[Chainsaw]

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

[Toba]

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.

[K-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?

#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;
             }
}

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.

[Toba]

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:

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 If

This code is untested, but it will work.

[Asif_NSU]

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

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

}

[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);
}

[Asif_NSU]

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.

#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();
}

[K-1]

Ah, i see where I made that mistake. That's what you get for doing recursion at 3am ;)

[Chainsaw]

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.

[Chainsaw]

The other problem with my code is that it is slow and uses a ton-o-stack. I don't see how a recursive function really buys enough in simplicity to warrent the stack usage and overhead of function calls.

Also, it would be better to start testing at 2 and going up, because half of all integers are divisible by 2, and a third are divisible by 3, and so on.

So, given that, I think your original code is pretty good. Run the loop up to sqrt(n) rather than n, and maybe (A) test for 2 as a special case, and (B) run the loop from 3 up and increment by 2 since no even numbers would be prime and this would save 50% of the tests worst-case.

[Toba]

You know, I just remembered that I did this two years ago in QBASIC. Here's my code:

100 Cls
200 INPUT "WHAT NUMBER DO YOU WANT TO CHECK FOR PRIMENESS?  ", NUMCHECK#
300 GoTo 500
400 Print "WHAT NUMBER DO YOU WHAT TO CHECK FOR PRIMENESS?  ", NUMCHECK#
500 Print "PROCESSING..."
600 NUMCHECK# = Fix(NUMCHECK#)
550 MAXCHECK# = Sqr(NUMCHECK#)
700 NUMDIVD# = 2
800 QUOTIENT# = NUMCHECK# / NUMDIVD#
900 RNDDQTNT# = Fix(QUOTIENT#)
1000 If RNDDQTNT# = QUOTIENT# Then GoTo 1700
1100 NUMDIVD# = NUMDIVD# + 1
1200 GoTo 1400
1300 NUMDIVD# = NUMDIVD# + 2
1400 If NUMDIVD# < MAXCHECK# Then QUOTIENT# = NUMCHECK# / NUMDIVD# Else GoTo 2100
1500 RNDDQTNT# = Fix(QUOTIENT#)
1600 If RNDDQTNT# = QUOTIENT# Then GoTo 1700 Else GoTo 1300
1700 Print NUMCHECK#; "IS NOT PRIME"
1800 Print "DIVISIBLE BY"; QUOTIENT#
1900 Print "DIVISIBLE BY"; NUMDIVD#
2000 GoTo 2200
2100 Print NUMCHECK#; "IS PRIME"
2200 Beep
2250 Print ""
2300 Print "        OPTIONS"
2400 Print "DO ANOTHER Y/N/1/2 "
2500 Print "PRESS y TO GO THROUGH THE ENTIRE PROGRAM AGAIN"
2600 Print "PRESS n TO QUIT"
2700 Print "PRESS 1 TO CHECK PRIMENESS OF FIRST FACTOR"
2800 Print "PRESS 2 TO CHECK PRIMENESS OF SECOND FACTOR"
2900 A$ = INKEY$
3000 If A$ = "" Then GoTo 2900
3100 If A$ = "n" Then GoTo 3800
3200 If A$ = "y" Then GoTo 100
3300 If A$ = "1" Then NUMCHECK# = QUOTIENT#: Cls: GoTo 400
3400 If A$ = "2" Then NUMCHECK# = NUMDIVD#: Cls: GoTo 400
3700 GoTo 2900
3800 End

I didn't seem to know how to do a normal loop back then, but it works (I think).

[wolfstrike]

ahhh BASIC programming , when programming was easy and FUN.