如何检查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; 
}