如何檢查no是否是階乘？

Question

我有一個問題，然後給了一些輸入數字n，我們必須檢查no是否是其他否的因子。

輸入24，輸出真正
INPUT 25 OUTPUT假
我寫了下面的程序吧： -

int factorial(int num1) 
    { 
     if(num1 > 1) 
     { 
      return num1* factorial(num1-1) ; 
     } 
     else 
     { 
      return 1 ; 
     } 
    } 

    int is_factorial(int num2) 
    { 
     int fact = 0 ; 
     int i = 0 ; 
     while(fact < num2) 
     { 
      fact = factorial(i) ; 
      i++ ; 
     } 
     if(fact == num2) 
     { 
      return 0 ; 
     } 
     else 
     { 
      return -1; 
     } 
    } 

這兩個函數，似乎正常工作。
當我們反覆提供大量輸入時，is_factorial將反覆調用factorial，這真是浪費時間。
我也試過維護一個階乘爲因子

所以，我的問題是，有一些更有效的方法來檢查一個數字是否是階乘？

Answer 1

這是浪費計算階乘持續這樣的，因爲你複製在x!所做的工作，當你做(x+1)!，(x+2)!等。

---

一種方法是維護給定範圍內的階乘列表（例如所有64位無符號階乘因子），並將其與之進行比較。鑑於因子增長的速度有多快，該列表不會很大。事實上，這裏有一個C元程序，實際上爲您生成的功能：

#include <stdio.h> 

int main (void) { 
    unsigned long long last = 1ULL, current = 2ULL, mult = 2ULL; 
    size_t szOut; 

    puts ("int isFactorial (unsigned long long num) {"); 
    puts (" static const unsigned long long arr[] = {"); 
    szOut = printf ("  %lluULL,", last); 
    while (current/mult == last) { 
     if (szOut > 50) 
      szOut = printf ("\n  ") - 1; 
     szOut += printf (" %lluULL,", current); 
     last = current; 
     current *= ++mult; 
    } 
    puts ("\n };"); 
    puts (" static const size_t len = sizeof (arr)/sizeof (*arr);"); 
    puts (" for (size_t idx = 0; idx < len; idx++)"); 
    puts ("  if (arr[idx] == num)"); 
    puts ("   return 1;"); 
    puts (" return 0;"); 
    puts ("}"); 

    return 0; 
} 

當您運行的是，你得到的功能：

int isFactorial (unsigned long long num) { 
    static const unsigned long long arr[] = { 
     1ULL, 2ULL, 6ULL, 24ULL, 120ULL, 720ULL, 5040ULL, 
     40320ULL, 362880ULL, 3628800ULL, 39916800ULL, 
     479001600ULL, 6227020800ULL, 87178291200ULL, 
     1307674368000ULL, 20922789888000ULL, 355687428096000ULL, 
     6402373705728000ULL, 121645100408832000ULL, 
     2432902008176640000ULL, 
    }; 
    static const size_t len = sizeof (arr)/sizeof (*arr); 
    for (size_t idx = 0; idx < len; idx++) 
     if (arr[idx] == num) 
      return 1; 
    return 0; 
} 

這是相當短的，高效的，甚至64位析因。

---

如果你是一個純粹的編程方法（沒有查找表）後，您可以使用一個階乘數是屬性：

1 x 2 x 3 x 4 x ... x (n-1) x n 

爲n一些價值。

因此，您可以簡單地開始將測試編號除以2，然後3然後4等。兩件事情之一會發生。

首先，您可能會得到一個非積分結果，在這種情況下，其不是的因子。

其次，您可能以1從該部門結束，在這種情況下它是的因子。

假設你的部門是不可或缺的，下面的代碼將是一個很好的起點：

int isFactorial (unsigned long long num) { 
    unsigned long long currDiv = 2ULL; 
    while (num != 1ULL) { 
     if ((num % currDiv) != 0) 
      return 0; 
     num /= currDiv; 
     currDiv++; 
    } 
    return 1; 
} 

---

然而，對於效率，最好的選擇可能是第一個。將計算成本移至構建階段，而不是在運行時。如果計算成本與查表相比較顯着，則這是一種標準技巧。

你可能甚至通過使用查找表的二進制搜索甚至可以使模式有效，但考慮到其中只有二十個元素，這可能不是必需的。

Answer 2

如果數字是因子，那麼它的因子是1..n對於某些n。

假設n爲整數變量，我們可以執行以下操作：

int findFactNum(int test){ 
    for(int i=1, int sum=1; sum <= test; i++){ 
    if(sum == test) 
     return i; //Factorial of i 
    sum *= i; //Increment factorial number 
    } 
return 0; // factorial not found 
} 

現在數24傳遞給該功能塊，它應該工作。該函數返回剛剛通過的因子的數字。

Answer 3

通過簡單檢查數字是奇數還是偶數（使用％2），可以加速至少一半的情況。沒有奇數（不包括1）可以是任何其它數的階乘

Answer 4

#include<stdio.h> 
main() 
{ 
     float i,a; 
     scanf("%f",&a); 
     for(i=2;a>1;i++) 
     a/=i; 
     if(a==1) 
     printf("it is a factorial"); 
     else 
     printf("not a factorial"); 
} 

Answer 5

public long generateFactorial(int num){ 
    if(num==0 || num==1){ 
     return 1; 
    } else{ 
     return num*generateFactorial(num-1); 
    } 
} 
public int getOriginalNum(long num){ 
    List<Integer> factors=new LinkedList<>(); //This is list of all factors of num 
    List<Integer> factors2=new LinkedList<>();  //List of all Factorial factors for eg: (1,2,3,4,5) for 120 (=5!) 
    int origin=1;    //number representing the root of Factorial value (for eg origin=5 if num=120) 
    for(int i=1;i<=num;i++){ 
     if(num%i==0){ 
      factors.add(i);  //it will add all factors of num including 1 and num 
     } 
    } 

    /* 
    * amoong "factors" we need to find "Factorial factors for eg: (1,2,3,4,5) for 120" 
    * for that create new list factors2 
    * */ 
    for (int i=1;i<factors.size();i++) {   
     if((factors.get(i))-(factors.get(i-1))==1){ 

      /* 
      * 120 = 5! =5*4*3*2*1*1 (1!=1 and 0!=1 ..hence 2 times 1) 
      * 720 = 6! =6*5*4*3*2*1*1 
      * 5040 = 7! = 7*6*5*4*3*2*1*1 
      * 3628800 = 10! =10*9*8*7*6*5*4*3*2*1*1 
      * ... and so on 
      * 
      * in all cases any 2 succeding factors inf list having diff=1 
      * for eg: for 5 : (5-4=1)(4-3=1)(3-2=1)(2-1=1)(1-0=1) Hence difference=1 in each case 
      * */ 

      factors2.add(i); //in such case add factors from 1st list " factors " to " factors2" 
     } else break; 
     //else if(this diff>1) it is not factorial number hence break 
     //Now last element in the list is largest num and ROOT of Factorial 
    } 
    for(Integer integer:factors2){ 
     System.out.print(" "+integer); 
    } 
    System.out.println(); 

    if(generateFactorial(factors2.get(factors2.size()-1))==num){ //last element is at "factors2.size()-1" 
     origin=factors2.get(factors2.size()-1); 
    } 
    return origin; 

    /* 
    * Above logic works only for 5! but not other numbers ?? 
    * */ 
} 

Answer 6

可以創建包含階乘列表中的一個陣列：
像在下面我創建包含階乘到陣列中的代碼20. 現在你只需要輸入的數量和檢查是否有數組或不..

#include <stdio.h> 
int main() 
{ 
    int b[19]; 
    int i, j = 0; 
    int k, l; 

    /*writing factorials*/ 
    for (i = 0; i <= 19; i++) { 
     k = i + 1; 
     b[i] = factorial(k); 
    } 
    printf("enter a number\n"); 
    scanf("%d", &l); 
    for (j = 0; j <= 19; j++) { 
     if (l == b[j]) { 
      printf("given number is a factorial of %d\n", j + 1); 
     } 
     if (j == 19 && l != b[j]) { 
      printf("given number is not a factorial number\n"); 
     } 
    } 
} 
int factorial(int a) 
{ 
    int i; 
    int facto = 1; 
    for (i = 1; i <= a; i++) { 
     facto = facto * i; 
    } 
    return facto; 
}