如何在计算质因数时提高执行时间

Question

如何在计算质因数时提高执行时间

cmathfactorialprime-factoring

5

我需要编写一个程序来查找展示n!（排除1）的最大方法。

例如：4！= 1x2x3x4 = 1x2x3x2x2。因此，您可以使用5个数字的乘积来显示4！。因此，输入为4，输出为5。 5是您可以用来表示4！的最大数字数量。

简单地说，就是将阶乘数分解为质因数，计算它们的数量并显示出来。

我使用了一个“for”循环来计算1到“n”的所有质因数及其数量。

但是当“n”为100000时，速度很慢，需要8秒才能完成。我需要提高速度。

我认为问题在于分解函数。

int factors( int fact )
{
    int i,cont,product=1, control;
    cont=0;
    control=fact;
    for (i= 2;control != product;)
    {
        if ((fact%i == 0))
        {
            cont++;
            fact/=i;
            product*=i;}
        else
        i++;
    }
    return cont;
}

我需要改进它以获得最佳执行时间。或者，我用来从阶乘数中获取质因数的方法可能不是一个好选择？

注意：我不计算100000！的值。我只分解从1到10000的所有数字并计数。

- exsnake

6

“4!” 不等于 “1x2x3x4x5”，它的值为24。 - Fiddling Bits

3

只是想澄清一下，您正在尝试计算100000!的值吗？您有没有任何想法这个数字有多大？ - Greg Hewgill

3

顺便提一下，你可以把它看作是一道算术（或数论）数学练习。提示：你可能不需要计算100!来得到它的最大质因数。 - Basile Starynkevitch

2

如果输入是7！，输出为8（2x3x2x2x5x2x3x7）... 我不是在计算7!的值，而是质因数的数量。 - exsnake

1

@FiddlingBits 告诉我的老师吧，哈哈。如果你不在意需要多长时间来解决这个问题，我认为这并不是一个难题。执行时间并不是作业的要求，我只是着迷于提高执行时间。 - exsnake

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- BLUEPIXY · Accepted Answer

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int *prime;
int prime_n;

void make_prime_table(int n){
    prime = malloc(sizeof(int) * n / 2);
    prime_n =0;
    prime[prime_n++] = 2;
    prime[prime_n++] = 3;
    int i, j;
    for(i = 5; i <= n; i +=2){
        bool is_prime = true;
        for(j = 1; j < prime_n ; ++j){
            int t = prime[j];
            if(t * t > i)
                break;
            if(i % t == 0){
                is_prime = false;
                break;
            }
        }
        if(is_prime)
            prime[prime_n++] = i;
    }
}

int factors(int fact_n ){
    int i, c, p, sum=0;
    for(i = 0; i < prime_n ; ++i){
        c = fact_n;//number of prime in N : (x1 = N / P) + (x2 = x1 / P) + ...
        while(c = c / prime[i]){
            sum += c;
        }
    }
    return sum;
}

int main(void){
    int n = 100000;
    make_prime_table(n);
    int ans = factors(n);
    printf("ans = %d\n", ans);

    free(prime);
    return 0;
}

在N!中，素数P的数量为：
10!中2的情况

1 2 3 4 5 6 7 8 9 10
  *   *   *   *    * # There are 5 number that is divided by 2. 5 = 10 / 2  
      *       *      # Number that can be divided further part of the mark of `*`(5/2).  
              *      # The number of total is the number of `*`.

*搜索“勒让德定理”