How to improve execution time when calculating prime factors

Question

I have to make a program to find the largest way to show a n! number (excluding the 1).

for example: 4! = 1x2x3x4 = 1x2x3x2x2. so you can use the product of 5 numbers to show the 4!. so the imput is 4 and the output is 5. 5 is the max amount of numbers with which you can express the 4!.

In simple words is factorize a factorial number in prime factors, count how many they are and show it.

What I did was a 'for' cycle where I count all the prime factors of 1 to 'n' and amount of them.

But I have a problem with big numbers like when 'n' is 100000, it takes 8 seconds to complete. I need to improve the speed.

I think the problem is in the factorization function.

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;
}

I need to improve it to get a best execution time. Or maybe the method that i'm using to get the prime factors from a factorial number isn't a good option?

NOTE: I do not calculate the value of 100000!. I just factorize all the numbers from 1 to 10000 and count them.

Answer 1

#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;
}

---

number of prime P in N! :
case of 2 in 10!

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 `*`.  

*search "theorem of Legendre"