How to find prime numbers in C using recursion

Question

I am writing a program to find the prime numbers in C using recursion. Here is the program I've written.

#include<stdio.h>
#include<conio.h>

void rec(int, int);
int main()
{
    rec(2,2);
    getch();
    return 0;
}
void rec(int n, int x)
{
    if(x>999)
        return;
    if(n==x)
    {
        printf("%d ,", x);
        rec(2,x+1);
        return;
    }
    if(x%n==0)
    {
        rec(2,x+1);
        return;
    }
    rec(n+1,x);
}

I don't know what is wrong in it, it is working well till 887 by crashes after it. To check, just replace x>999 by x>300, it will work, but not for x>999. Please tell the fault in the program instead of writing a whole new program.

Answer 1

Recursion depth likely exceeded.

Recursion depth appears to go up proportional to the square of the limit.
Try

#include <stdio.h>
int depth = 0;
int maxdepth = 0;

void rec(int n, int x) {
  depth++;
  if (depth > maxdepth) maxdepth = depth;
  if (x > 860) {
    depth--;
    return;
  }
  if (n == x) {
    printf("%d ,", x);
    rec(2, x + 1);
    depth--;
    return;
  }
  if (x % n == 0) {
    rec(2, x + 1);
    depth--;
    return;
  }
  rec(n + 1, x);
  depth--;
}

int main(void) {
  rec(2, 2);
  printf("\n depth %d maxdepth %d\n", depth, maxdepth);
  return 0;
}

max depth 60099 (and that is with limit 860)

Code needs a less depth intensive approach.

Try dividing n by all primes 2 to sqrt(n). If number of even, it in a prime only of 2. Else if below 7, it is a prime if not 1. Else to find a prime above 7, add 2 to previous prime candidate and recursively test if it is a prime. So you have 2 functions bool is_prime(n) and unsigned next_prime(n) calling each other.

max depth : 3 for all 1000

Like OP's self description, in this case "And too lazy to tell anything further."

Answer 2

#include<stdio.h>

void rec(int test_number, int prime_index);

int main(void){
    rec(2, 0);

    return 0;
}

void rec(int n, int i){
    static int prime[500], cp;//for memorize
    if(n > 999)
        return;
    if(prime[i] == 0 || prime[i]*prime[i] > n){//prime[i]*prime[i] > n : To reduce the depth of recursion by narrowing the upper limit of the test.
        printf("%d, ", n);
        prime[cp++] = n;
        rec(n + 1 + (n != 2), 0);//n != 2 : Avoid an even number of other than 2
        return;
    }
    if(n % prime[i]==0){
        rec(n + 1 + (n != 2), 0);
        return;
    }
    rec(n, i+1);
}

Answer 3

You can try finding prime numbers between 1 and a given integer N (list of prime numbers in a range) using the below code :

#include<stdio.h>
void main()
{
    int n,flag=0,i,j;
    printf("Enter range of prime number : ");
    scanf("%d",&n);
    printf("\nPrime numbers are : ");
    for(i=1;i<n;i++)
    {
        flag=0;
        for(j=2;j<i;j++)
        {
            if(i%j==0)
            {
                flag=1;
                break;
            }
            else
                flag=0;
        }
        if(flag==0)
            printf("\n%d",i);
    }
}

Answer 4

PROBLEM: Recursion of rec function many times under different conditional statements lead to increase in depth of recursion.

SOLUTION: Decrease the use of rec function under conditional statements by having a loop in main function to pass number under checking (prime or not) in rec function.

#include<stdio.h>
void rec(int,int);
int main()
{
    int i=2;
    while(i<=1000) //passing 2,3,4...,1000 (one by one) in rec function to check if it is prime or not
    {
        rec(2,i);
        i++;
    }
}
void rec(int n,int x)
{
    if(n==x) //if number(n) by which divisibility is checked and number(x or i) which is under checking gets equal then number(x or i) is proved as prime and get printed
        printf("%d, ", x);
    else if(x%n!=0) //if number(x or i) under checking is not divisible by number(n) then call rec function again to check divisibility of number(x) by number(n+1)
        rec(n+1,x);
//if number(x or i) under checking is divisible by number(n) at any stage then return to main function and next number(i++ or new x) is passed to rec function to check if it is prime or not
}

SUGGESTION: Recursive functions are interesting. But printing prime numbers using recursive function or any simple method to a large limit like(10^6) is very slow. Use Sieve of Eratosthenes (fast, simple and interesting) or some modified version (fastest) of it to print prime numbers to any extent very quickly. Also try to learn Sieve of Sundaram (it is also slow but interesting) and Sieve of Atkin (fast and interesting but complex).