언더프라임 | 1124번

문제

자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다.
ㅤ
어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. 12는 목록에 포함된 소수의 개수가 3개이고, 3은 소수이니 12는 언더프라임이다.
ㅤ
두 정수 A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 정수 중에서 언더프라임인 것의 개수를 구해보자.

풀이

• 소인수분해 시 필연적으로 n을 나눈 인수중 1개 이상은 n의 제곱근 보다 작거나 같음
  ㄴ> ex) n=16 / 16의 제곱근 4 / 16 = 2x2x2x2 / 나누어진 인수가 4보다 작음
  ㄴ> ex) n=10 / 10의 제곱근 3 / 10 = 2x5 / 나눈 인수중 1개는 10의 제곱근 3보다 작음
  ( 그 외 나머지(10 % 3 == 5) 는 소수이므로 그 값을 카운팅만 해주면 됨)

다른 사람 풀이

• 다른분이 푸신거 찾아봤는데 곱셈을 통해 소수 개수 count가 어떻게 성립되는지 아직도 이해는 안되지만 ..굉장히 빠른걸로 봐서는 소인수분해 카운팅에 최적화된 코드인 것 같아 가져와봤다.
  

결과