12908 - Number of factorial’s factors

#include <stdio.h>

int cnt[100000];
int prime[100000];

int main(){
    int N;
    scanf("%d", &N);
    for(int i = 2; i <= N; i++){
        for(int j = 2; j <= i; j++){
            if(i % j == 0 && i!= j){
                // a number is not a prime if it can be divided by other number, so just break it
                prime[i] = 0;
                break;
            } else {
                // else it is a prime, because it can only be divided by its own number
                prime[i] = 1;
            }
        }
        // printf("i = %d, prime = %d\n", i, prime[i]);
    }

    int temp = 0; // store i so that i can iterate how many time it can be divided by j (the count)
    int total = 0;
    for(int i = N; i >= 2; i--){
        temp = i;
        for(int j = 2; j <= N; j++){
        // got (6/7) cuz < not <=, it is <= because it applies for 2! and 3!
        // because 2! is 2x1 which is a prime number if i didn't put <= it won't iterate the 2
            if(prime[j] == 1){ //if prime
                while(temp >= j && temp % j == 0){
                    // iterate if temp is still more than the prime number, and if it's divisible by the number
                    // e.g 4/2 = 2, 2/2 = 1 -> iterate this
                    temp = temp / j;
                    cnt[j]++;
                    //printf("cnt[%d] = %d\n", j, cnt[j]);
                }
            }
        }
    }
    unsigned long long final = 1; // variable to store to use at legendre formula
    for(int i = 2; i <= N; i++){
        if(cnt[i] == 0) continue;
        else {
            cnt[i] = cnt[i]+1;
            final *= cnt[i];
            //printf("cnt[%d] = %d\n", i, cnt[i]);
        }
    }
    printf("%llu", final);
    return 0;
}
// notes :
// first, I check for prime and store it in an array with 1 and 0 as the element
// 1 is true and 0 is false
// Then, use loops to iterate N! (not by calculating the results), n, n-1, n-2, n-3, ....., 2, 1
// actually 1 does not matter (so we can just stop the loop when it reaches 2)
// then, each time the loops iterate, we check if the i is divisible right now by prime numbers
// if it's still, then keeps dividing until it reaches 1, or until temp < j
// e.g 4 -> 4/2 = 2 (1st loop) 2/2 = 1 (2nd loop) then loop stops because 1 < 2
// remember to count how many times, I make another array to store how many count in the respective prime number
// then with the legendre formula, make a loop and cnt[i] += 1; then multiply everything
// don't forget that if the count in the loop is zero we can just ignore it, if(cnt[i] == 0) continue;