1

用 N! 表示的非负整数 N 的阶乘是所有小于和等于 N 的正整数的乘积。任何数的阶乘都可以以其素因数的最简单形式表示。例如 4!=4*3*2*1= (2^3)*(3^1) 阶乘也可以通过每个素因数出现的次数来指定，因此 24 可以指定为 (3 1)意思是3个二，1个三。我写的代码给出了小数字的答案，但是当数字变大时，程序不会返回答案

#include<stdio.h>

long fact(long n)
{
    if(n==0)
        return 1;
    else
        return(n*fact(n-1));
}

int main()
{
    long a[10]={0};
    long n,l=0,count=0,i,j,flag;
    if(!scanf("%ld",&n))
    {
        printf("Invalid input");
        goto l1;
    }

    if(n<0)
    {
        printf("Invalid input");
        goto l1;
    }

    n=fact(n);

    while(n%2==0)
    {
        count++;
        n=n/2;
    }

    a[l]=count;
    l++;

    for(i=2;i<=n;i++)
    {
        count=0;
        j=2;
        flag=0;
        while(j<i)
        {
            if(i%j==0)
            {
                flag=0;
                break;
            }
            else
                flag=1;
            j++;

        }

        if(flag==1)
        {
            count=0;
            while(n%i==0)
            {
                count++;
                n=n/i;
            }
            a[l]=count;
            l++;
        }
    }

    for(i=0;i<l;i++)
        printf("%ld ",a[i]);

l1:return 0;

}
4

4 回答 4

3

你不能存储 n! 值，即使在结果增长极快的情况下也是如此。您应该修改您的算法：计算每个数字的素因子分解2，n并递归地添加 n-1, n-2... 的分解

例如，假设您使用 10! 来执行此操作。（有1省略）

2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10.

现在，这些中的每一个都是素数。

2  : 2
3  : 3
4  : 2 * 2
5  : 5
6  : 2 * 3
7  : 7
8  : 2 * 2 * 2
9  : 3 * 3
10 : 2 * 5

这10!相当于：

2 * 3 * 2 * 2 * 5 * 2 * 3 * 7 * 2 * 2 * 2 * 3 * 3 * 2 * 5

从上面的项中累积每个素^数的计数，我们有以下内容，表示取幂，而不是 XOR 的 C 运算符）

2^8 * 3^4 * 5^2 * 7^1

所以答案是(8 4 2 1)。检查我们的工作，我们得到：

2^8 = 256
3^4 = 81
5^2 = 25
7^1 = 7

7 * 25 * 81 * 256 = 3628800

我的计算器告诉我...

10! = 3628800

所以算法是正确的。n最后请注意，在这种情况下，我们不需要对任何大于 的数字进行质因数10。

注意：避免gotos

于 2013-08-20T15:53:40.317 回答
2

问题是这一行与溢出相结合：

for(i=2;i<=n;i++)

只要 n 可以分解为大量的小素数，这工作得很好，条件阶乘满足。没问题。当您的阶乘不再表示为 long 时，问题就开始了。然后结果将是 long 值范围内的某个其他数字，它可能具有非常大的素数因子，或者本身就是素数。

现在我假设，您正在一个 long 为 64 位的平台上工作（您可以通过打印 的值来检查sizeof(long)），因此这些大素数可以在 10^18 的范围内。即使是最现代、最快的硬件也无法在你的一生中循环遍历所有这些数字。因此，当您仍在等待时，该循环不会终止。

唯一的出路是确保您的计算不会溢出。您可以在每次乘法后检查结果除以一个因子是否产生另一个因子。如果没有，则您有溢出，应该退出并出现错误。

于 2013-08-20T20:30:23.343 回答
0

您的方法有两个主要障碍：

  1. A long，甚至 anunsigned long都不足以容纳大多数数字的阶乘。Along通常存储 32 位（尽管这可能因架构而异），这允许我们存储小于 的数字2**32 - 1，大约为 40 亿。13！已经比那个大了。

  2. 当编译器不进行尾递归优化时，由于在调用堆栈中为函数分配空间的开销，太多的递归调用会严重影响性能。

更好的解决方案是使用大整数（可以增长到任意大小）或使用双精度浮点数并使用迭代解决方案来找到近似解决方案。

另一方面：不赞成goto在 C 中使用 of。改为使用if, else, for, while, switch。把这种想法留给汇编编程吧。

于 2013-08-20T18:40:33.787 回答
0

没有有效的算法来分解大数。虽然可能不是您所期望的答案，但请查看维基百科： http ://en.wikipedia.org/wiki/Integer_factorization

于 2013-08-20T15:07:41.173 回答