Prime factors in c by using only recursion

Question

I wrote this program in C for prime factors but its crashing after printing first prime factor, So i need help

#include<stdio.h>
void prime(int n,int i)
{
    i=2;
    if(n%i==0)
    {
        printf("%d ",i);
        n=n/i;
        prime(n,i);
    }
    else
    {
        i++;
        prime(n,i);
    }
}
void main()
{
    int n;
    scanf("%d",&n);
    prime(n,2);
}

Note that `prime` *always* calls itself, violating the Prime Directive of Recursion. — Scott Hunter, May 31 '18 at 13:33
Do a google search in how to debug a program. Also, first thing in your prime function sets a parameter to a fixed value? Whats the point of passing the parameter then? — Jorge.V, May 31 '18 at 13:33
Where is the recursion terminal case. ie. When will `prime` ever return? — acraig5075, May 31 '18 at 13:34
I was confused in returning so i used printf instead of return — Alind, May 31 '18 at 13:35
okay @WeatherVane now all prime factors are getting printed but its still crashing after printing all prime factors — Alind, May 31 '18 at 13:40
Then all the comments that were not about i=2 still apply, don't they? If you use the algorithm by hand, you stop at some point, or you would continue all your life. So when should the program stop? — Arndt Jonasson, May 31 '18 at 13:47

Trevor Tracy · Answer 1 · 2018-05-31T14:53:45.003

2

#include<stdio.h>
void prime(int n,int i)
{
    if(n==0)
        ;
    if(n==1)
        ;
    else if(n%i==0){
        printf("%d ", i);
        n=n/i;
        prime(n,i);
    }
    else{
        i++;
        prime(n,i);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    prime(n,2);

    return 0;
}

If you add the cases for n==0 and n==1 (and remove the i=2;), you'll be all set.

edit - removed voided main as suggested by Jonathan Leffler

edited May 31 '18 at 14:53

answered May 31 '18 at 13:50

Trevor Tracy

356
1
10

Now that the program more or less works, it's time to point out that recursion is not a good substitute for loops in C. Try for example the number 3167361. I don't know its factors, but it overruns the stack for me. – Arndt Jonasson May 31 '18 at 13:55
And it's also not really very efficient: it tries all composite `i` although their factors have already been divided away. But as a first try, it's a good program. – Arndt Jonasson May 31 '18 at 14:00
The factors of that are: 1, 3, 9, 351929, 1055787, 3167361 – Trevor Tracy May 31 '18 at 14:02
The prime 351929 alone is sufficient to exhibit the problem. – Arndt Jonasson May 31 '18 at 14:05
Thank You @ArndtJonasson – Alind May 31 '18 at 14:12
Note that 9 is not a prime factor (and neither is 1): the prime factors of 3167361 are 3, 3 and 351929. – Jonathan Leffler May 31 '18 at 14:37
I listed all the factors @JonathanLeffler , not prime factors. But yes, you are correct – Trevor Tracy May 31 '18 at 14:39
See [What should `main()` return in C and C++?](https://stackoverflow.com/questions/204476/) for a discussion of why `void main()` is dubious — supported only on Windows. I realize you probably just copied the code from the question, but … – Jonathan Leffler May 31 '18 at 14:45
@AlindKumar you might be interested in this [Prime Factors Calculator](http://www.javascripter.net/math/calculators/primefactorscalculator.htm) to check your work. – Weather Vane May 31 '18 at 14:48

Nox · Answer 2 · 2018-05-31T13:42:35.773

1

It's doing an infinite loop as you are resetting i every time when doing

i = 2;

But even without that, you'll probably overflow i and you don't have a recursion terminal case.

you will have to rethink your logic for this to work.

edited May 31 '18 at 13:42

answered May 31 '18 at 13:41

Nox

932
1
9
27

okay now all prime factors are getting printed but its still crashing after printing all prime factors – Alind May 31 '18 at 13:42
Can u give me a hint – Alind May 31 '18 at 13:45
I'm sorry but you should really try to do this yourself. [SO rules](https://stackoverflow.com/help/on-topic) – Nox May 31 '18 at 13:50

Prime factors in c by using only recursion

2 Answers2