2312)수 복원하기

https://www.acmicpc.net/problem/2312

어떤 수를 소인수분해하려면 그 수 이하의 소수로 나눌 수 없을 때까지 나눠봐야 한다.

에라토스테네스의 체로 100000 이하의 소수를 미리 구해놓는다.

주어진 수를 2부터 그 수까지 소수로 나눌 수 없을 때까지 나누고

나누어지는 경우 그 소수를 하나 카운팅한다.

#include<stdio.h>
#define MAX 100000
 
typedef enum _BOOL {
    TRUE = 1, FALSE = 0
}BOOL;
 
void initArray(int A[MAX + 1], int n) {
    for (int i = 0; i < n; i++) {
        A[i] = 0;
    }
}
 
int main() {
    BOOL prime[MAX + 1];
    int cntPrime[MAX + 1] = { 0 };
    int n, Q, t, value;
 
    for (int i = 0; i <= MAX; i++) {
        prime[i] = TRUE;
    }
 
    for (int i = 2; i*i <= MAX; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= MAX; j += i) {
                prime[j] = FALSE;
            }
        }
    }
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &value);
 
        Q = value;
        t = 2;
        initArray(cntPrime, value);
 
        while (Q > 1) {
            if (Q%t == 0) {
                cntPrime[t]++;
                Q /= t;
            }
            else {
                while (prime[++t] != TRUE);
            }
        }
 
        for (int i = 2; i <= value; i++) {
            if (cntPrime[i] > 0) printf("%d %d\n", i, cntPrime[i]);
        }
    }
 
    return 0;
}