다시 질문방을 찾게 되었습니다;;

소인수분해를 하면 약수의 갯수를 찾을 수 있을것 같아서 아래와 같이 프로그래밍을 했습니다.

동작상 이상이 없는것 처럼 보이는데 2가지 문제가 있습니다;;

1) 예제 입력의 3번째, 200 1000000 2000000 의 답이 19 가 아닌 12가 나옴
2) 시간초과 발생

혹시 제가 생각을 잘못하고 만든 코드 인지 답답하여, 문제 해결하신 분들과 고수님들 에게 조언을 부탁드립니다;;

[[비밀번호 486|problem:PASS486]]

#include <stdio.h>
#include <time.h>

int TC;
unsigned long num,lo,hi;
unsigned long cnt;

unsigned long idx;
unsigned long ARR[25];  // 2^24 = 16,777,216 , so 25 is enough as max idx.

unsigned long pivot;
unsigned long prime_factor;

unsigned long result;

int main(void)
{
    scanf("%d",&TC);

    for(int i=0;i<TC;i++)
    {
        scanf("%lu %lu %lu",&num,&lo,&hi);
        
clock_t start = clock();

        for(unsigned long j=lo;j<=hi;j++)
        {
            // init
            pivot = prime_factor = j;
            idx = 0;
            for(unsigned long m=0;m<25;m++)
                ARR[m] = 0;


            // find prime factor
            for(unsigned long n=2;n<=pivot;n++)
            {
                if(prime_factor%n==0) {
                    ARR[idx] = n;
                    idx++;
                    prime_factor = prime_factor/n;
                    n = 1;
                    pivot = prime_factor;
                }
                else
                {
                    if(pivot/n+1 < n) continue; // bug fix
                    pivot = pivot/n+1;
                }
            }


            // add last prime factor. upper code does not add last prime factor... ; bug fix
            if(prime_factor != 1) {
                ARR[idx] = prime_factor;
                idx++;
            }

#if 0
            // for debugging
            if(idx == 1) {
                printf("소수\n");
                cnt = 2;
            }
            else {
                for(int l=0;l<idx;l++) {
                    printf("%d ",ARR[l]);
                }
                printf("\n");
            }
#endif
            // count all divisors
            // 1. sort
            for(unsigned long k=0;k<idx;k++)
            {
                unsigned long temp = 0;
                for(unsigned long k2=k;k2<idx;k2++)
                {
                    if(ARR[k]>ARR[k2]) {
                        temp = ARR[k];
                        ARR[k] = ARR[k2];
                        ARR[k2] = temp;
                    }
                }
            }

            // 2. sum of each prime factor * num
            unsigned long val = ARR[0];
            unsigned long each_cnt = 1;
            cnt = 1;

            for(unsigned long k3=1;k3<=idx;k3++)
            {
                if(val == ARR[k3]) {
                    each_cnt++;
                }
                else {
                    cnt = cnt * (each_cnt+1);
                    val = ARR[k3];
                    each_cnt = 1;
                }
            }

            if(cnt == num) result++;

        }

        printf("%lu\n",result);
printf("time : %d\n",clock()-start);

        result = 0;
    }

    return 0;
}