C语言 递归函数来找到质因数

recursive func to find prime factors

提问by fuddin

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

我做了一个递归函数来找到一个数字的质因数，但它有一个错误，使 turbo c 退出。请帮忙

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

回答by IVlad

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 iwill have in (*)?

你认为i会有什么价值(*)？

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

不确定你想i从什么开始，但我很确定你不希望它是随机的。如果你想让它以 的值开头num，你需要num在阅读后赋值给它：

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

回答by neal aise

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

（有点太困了，无法编写好的代码......所以对于任何错误，我提前道歉：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);


}

回答by yakiro

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

c++ 中的完全递归解决方案（对于 c 用 printf 替换 cout 行）：

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

回答by Introvertis

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.

函数调用（递归）的次数等于质因数的个数，包括1。

回答by user5041802

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

我是在 C 中完成的。根据编译器的不同，可能需要在程序中进行细微的更改。

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

回答by bsliao

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

回答by Mayur Anklekar

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

回答by SATISH

It's a old question, but still I would love to provide my answer to it. [ Don't down vote it without trying my code. It works! ]

这是一个老问题，但我仍然很乐意提供我的答案。[不要在没有尝试我的代码的情况下投票。有用！]

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.

我们不需要编写函数来计算下一个素数。例如，如果 num 是 24 并且我们不断地将它除以 2 直到它不再能被 2 整除，那么 2 的其他倍数也不能整除这个数字。所以最终只有（可能）素数可以完美地整除任何正整数。

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

You can find video lecture and complete notes about it at C Program To Find Prime Factors of a Number using Recursion.

您可以在C Program To Find Prime Factors using Recursion 中找到有关它的视频讲座和完整注释。

回答by Prashant

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

回答by Will A

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?

同意 IVlad - 另外，当 num 为素数时会发生什么？递归函数将被调用多少次，例如 num = 7？