c - 如何找出质数出现了多少次？

Question

我需要编写一个程序来输入一个数字并以C语言的形式输出它的阶乘

4!=(2^3)*(3^1)

5!=(2^3)*(3^1)*(5^1)

我能够找到质数 2、3 和 5，但是如何计算它们出现了多少次？ (^3，^1，^1)

代码:

int main() {
    int num,i,count,n;
    printf("Enter to find prime numbers: ");
    scanf("%d",&n);

    for(num = 2; num<=n;num++) {
        count = 0;

        for(i=2;i<=num/2;i++) {
            if(num%i==0)
            {
                count++;
                break;
            }
        }

        if(count==0 && num!= 1)
            printf("%d ",num);
    }
    return 0;
}

Answer 1

在不涉及任何代码的情况下，我将解释您做事的方式存在什么问题......

假设您想要找到 5 阶乘的质因数。所以您这样做:

5! = 2 x 3 x 4 x 5 (这是您的外循环 (for(num = ...)

假设对于特定迭代，num = 4。然后，在 i 中进行另一次迭代，检查每个数字，直到 num/2 是一个因子。现在为小值 5!这不是问题。考虑一个更大的数字，比如 25!。在这种情况下，您的外循环将是:

25! = 1 x 2 x 3 x ... 22 x 23 x 24 x 25

现在你的外部迭代num走得更远。现在考虑数字 24。24/2 = 12。您的程序将打印 24 除以 12 的所有因数，恰好是 2、3、4、6 和 12。我是当然，这不是你想要的。

首先，不要尝试求大数的阶乘。您将遇到溢出问题。接下来，我给你一些指点，希望你能自己解决问题。这是一个非常酷的问题，所以我真的希望你能够解决它:

1. 研究素筛算法 ( http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes )。您将不会直接使用它，而只能使用这里提到的想法。
2. 创建两个数组。第一个将包含质因数，而下一个将包含阶乘中出现的因数总数。
3. 对于特定的num，您需要进行迭代，而不是使用您已使用的i，而是使用素数数组中的值。 3.1.使用 Barmar 解释的方法查找此 num 能被因子整除的次数，并更新 count 数组中相应的计数。
4. 打印出您获得的因数和计数。

最后，我认为这是一个很好的问题。它教您如何避免遇到溢出错误并仍然能够使用计算机解决问题。如果您愿意的话，它可以教您动态内存分配和内存管理技能。它还可以帮助您批判性地思考问题。你不值得-1。我已经提高了你的评分。

享受编程的乐趣，并不断批判性地思考程序中的每个设置。

干杯!