소인수분해

간단한 소인수분해 알고리즘.

 

for (int i = 1; i <= e; i++) {
  for (int j = 1; j <= e / i; j++) {
    count[i * j]++;
  }
}

 

나는 처음엔 두 수로 분해하는 알고리즘을 짰는데, 입력값이 100만 단위의 숫자가 되니 시간이 너무 오래 걸렸다.

그래서 소인수로 분해해서 지수를 곱해나가는 알고리즘을 짰는데, 역시 시간이 너무 오래 걸렸다.

 

가끔 사람의 방식에서 벗어나는 문제들을 만난다.

사람의 방식을 버릴 수 있을까? 당분간은 고민을 하고 있어야 겠다.