CODEWITHSUNDEEP
crecursion
user379888
user379888

Reputation:

recursive func to find prime factors

i made a recursive function to find the prime factors of a number but it has a bug which makes turbo c quit. please help

#include<stdio.h>
#include<conio.h>
int prime(int num);
int primefactor(int num,int i);
void main(void)
{
    int num;
    printf("Enter a number whose prime factors are to be calculated:");
    scanf("%d",&num);
    primefactor(num,i);
     i=num 
    getch();
}
int primefactor(int num,int i)
{
    if(i==2)
    return 1;
    if(num%i==0)
    {
        if(prime(num))
        {
            printf(",%d",num);
            num=num/i;
            i++;
        }


    }
    i--;
    primefactor(num,i);
    return 0;
}
int prime(int num)
{
    int i,flag;
    for(i=2;i<num;i++)
    {
        if(num%i==0)
    flag=0;
    }
    return flag;
}

Upvotes: 1

Views: 37973

Answers (12)

masterleo
masterleo

Reputation: 19

//ECMAscript oneliner to find prime factors using recursion
const pf = (n, f=2, A=[]) => !~-n ? A : n%f ? pf(n,++f,A) : pf(n/f,f,[...A,f])

//example
console.log(pf(60));

Upvotes: -1

Satish
Satish

Reputation: 173

We need not write function to calculate next prime number. If for example, num is 24 and we continously divide it by 2 until it is no longer divisible by 2, then no other multiples of 2 can divide the number either. So ultimately only(probably) prime numbers can perfectly divide any positive integer number.

Here is my code: (I've written source code for both iterative as well as recursive logic)

#include<stdio.h>  
  
void pfactors_rec(int, int);  
void pfactors(int);  
  
int main()  
{  
    int num;  
  
    printf("Enter a positive integer number\n");  
    scanf("%d", &num);  
  
    printf("\nPrime Factors of %d without using recursion\n", num);  
    pfactors(num);  
  
    printf("\nPrime Factors of %d using recursion\n", num);  
    pfactors_rec(num, 2);  
  
    return 0;  
}  
  
void pfactors_rec(int num, int count)  
{  
    if(num < 1)  
        return;  
    else if(num % count == 0)  
    {  
      printf("%d\n", count);  
      pfactors_rec(num / count, count);  
    }  
    else  
    {  
      pfactors_rec(num, count+1);  
    }  
}  
  
void pfactors(int num)  
{  
    int count;  
  
    for(count = 2; (num > 1); count++)  
    {  
        while(num % count == 0)  
        {  
            printf("%d\n", count);  
            num = num / count;  
        }  
    }  
    printf("\n");  
}

Upvotes: 0

neal aise
neal aise

Reputation: 895

(little too sleepy to write good code.. so am sorry in advance for any bugs :p )

a simpler non recursive version

printPrimeFactors(int num) {

  for (i = 2; i < sqrt(num); i=getNextPrime()) {
     if (num %i)
        printf("%d", i);
  } 

}

if you have to use recursion

void factorization(int x, int i=2)
{
   if(x==1)
    return;

   if(x%i==0&&isPrime(i))
   {
    printf("%d ",i);
    factorization(x/i,i);
   }
   else
    factorization(x,i+1);


}

Upvotes: 2

Mayur Anklekar
Mayur Anklekar

Reputation: 1

#include  <`stdio.h`>

void pf(int,int);

int main()

{

int a,i=2;

     printf("Enter the Number:\n");
     scanf("%d",&a);

     pf(a,i);
}

void pf(int x,int y)

{

   if(x==1)

   return 1;

    else
    {
       if(x%y==0)
       {printf("%d\t",y);
        pf(x/y,y);
       }

       else
       {
        y++;
        pf(x,y);
       }
    }
}

Upvotes: 0

bsliao
bsliao

Reputation: 1

// recursivePrime.cpp
// Purpose: factor finding for an integer 
// Author: Ping-Sung Liao, Kaohsiung,TAIWAN
// Date: 2017/02/02
// Version : 1.0
// Reference:
// http://stackoverflow.com/questions/3221156/recursive-func-to-find-prime-factors

#include<stdio.h>
#include<stdlib.h>
#include<math.h>


int primefactor(int num,int i);
int main(void)
{
    int num, i;
    printf("Enter a number whose prime factors are to be calculated:");
    scanf("%d",&num);
    i=int ( sqrt (num) );
    primefactor(num,i);

    system("pause");  // instead of getch()
}

int primefactor(int num,int i)
{   printf("num %d i=%d\n", num, i);
    if (i==1)
      printf("prime found= %d\n", num);  // prime appearing in he variuable num

    else if(num%i==0)
    {   primefactor( int (num/i) , int ( sqrt(num/i) ) );
        primefactor( i , int (sqrt ( i ) ) );       
    }
    else 
    {  i--;
       primefactor(num,i);
    }
    return 0;
}

Upvotes: 0

user5041802
user5041802

Reputation: 11

I did this in C. Depending on the compiler, minor changes might be needed to make in the program.

#include<stdio.h>
int primefact(int);
int main()
{
    int n;
    printf("Enter a number whose prime factors are to be calculated : \n");
    scanf_s("%d", &n);
    printf("Prime factors of %d are : ");
    primefact(n);
    printf("\n");
    return 0;
}
int primefact(int n)
{
    int i=2;
    while(n%i!=0)
        i++;
    printf("%d ", i);
    if(n==i)
        return 0;
    else
        primefact(n/i);
}

Upvotes: 1

Raj
Raj

Reputation: 479

Implementation in java..

public class PrimeFactor {

public int divisor=2;
void printPrimeFactors(int num)
{

    if(num == 1)
        return;

    if(num%divisor!=0)
        {
        while(num%divisor!=0)
            ++divisor;          
        }
    if(num%divisor==0){

    System.out.println(divisor);
        printPrimeFactors(num/divisor);
    }

}
public static void main(String[] args)
{
    PrimeFactor obj = new PrimeFactor();
    obj.printPrimeFactors(90);
}

}

Upvotes: -1

Prashant
Prashant

Reputation: 1

#include<stdio.h>
#include<stdlib.h>

int ar[10]={0};
int i=0,j=2;

void P(int n)
{
    if(n<=1){
        return ;
    }

    else{
            if(n%j == 0){
                printf("%d\t",j);
                n=n/j;  

            }
            else{
                j++;                
            }   
        P(n);
    }
}

int main(void)
{
    int n;
    printf("Enter n = ");
    scanf("%d",&n);
    P(n);
    printf("\n");
    return 0;
}

Upvotes: 0

Introvertis
Introvertis

Reputation: 11

The best way to implement prime factorization with low overhead function calls would be . . .

void factors(int number)
{
    int divisor = 2;
    if (number == 1) { cout << "1"; return; }
    while ((number % divisor) && (number > divisor)) divisor++;
    cout << divisor << ", ";
    factors(number / divisor);
}

The number of function calls (recursion) is equal to the number of prime factors, including 1.

Upvotes: 1

yakiro
yakiro

Reputation: 763

Full recursive solution in c++ (for c replace cout lines with printf):

void printPrimeFactors(int num)
{
    static int divisor = 2; // 2 is the first prime number

    if ( num == 1 ) //if num = 1 we finished
    {
        divisor = 2; //restore divisor, so it'll be ready for the next run
        return;
    }
    else if ( num % divisor == 0 )  //if num divided by divisor
    {
        cout << divisor << " "; //print divisor
        printPrimeFactors( num / divisor ); //call the function with num/divisor
    }
    else //if num not divided by divisor
    {
        divisor++; //increase divisor
        printPrimeFactors( num ); 
    } 
}

Upvotes: 1

Will A
Will A

Reputation: 24988

Agree with IVlad - also, what happens in the case when num is prime? How many times will the recursive function be called for e.g. num = 7?

Upvotes: 0

IVlad
IVlad

Reputation: 43477

void main(void)
{
    int num,i=num; // (*)
    printf("Enter a number whose prime factors are to be calculated:");
    scanf("%d",&num);
    primefactor(num,i);
    getch();
}

What value do you think i will have in (*)?

Not sure what you want i to start out as, but I'm pretty sure you don't want it to be something random. If you want it to start with the value of num, you need to assign num to it after you read it:

void main(void)
{
    int num,i; 
    printf("Enter a number whose prime factors are to be calculated:");
    scanf("%d",&num);
    i = num; // assignment goes here.
    primefactor(num,i);
    getch();
}

Upvotes: 5

Related Questions