遞歸函數來尋找素數因子

Question

我做了一個遞歸函數來找到一個數字的主要因素，但它有一個錯誤，使渦輪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; 
} 

Answer 1

（有點太困了，要寫出好的代碼..所以很抱歉，您的任何錯誤：P）

一個簡單的非遞歸版本

printPrimeFactors(int num) { 

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

} 

，如果你要使用遞歸

printPrimeFactors(int num) { 

if(isPrime(num)) { 
    printf ("%d ", num); 
} else { 
    for(i=2; i < sqrt(num); i++) { 
     if(num%i ==0) { 
       printPrimeFactors(i); 
       printPrimeFactors(num/i); 
     } 
    } 
} 

} 

Answer 2

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

你覺得什麼樣的價值i將在(*)？

不知道你想要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(); 
} 

Answer 3

同意IVlad - 此外，當num是首要的情況下會發生什麼？遞歸函數要調用多少次數字= 7？

Answer 4

C++中的完整遞歸解決方案（for 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); 
    } 
} 

Answer 5

通過低開銷函數調用實現素分解的最佳方式是。 。 。

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

的函數調用（遞歸）的數量相等的素因子的數量，其中包括1

Answer 6

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

Answer 7

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

} 

Answer 8

我這樣做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); 
} 

Answer 9

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