[백준/Python] Silver I #1124 언더프라임

1124번: 언더프라임

문제

자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다.

어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. 12는 목록에 포함된 소수의 개수가 3개이고, 3은 소수이니 12는 언더프라임이다.

두 정수 A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 정수 중에서 언더프라임인 것의 개수를 구해보자.

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 언더프라임 개수를 출력한다.

풀이

import math
import sys
input = sys.stdin.readline
a, b = map(int,input().split())

def is_prime_num(n):
  for i in range(2, int(math.sqrt(n))+1):
      if n % i == 0:
        d[n] = d[n//i] + 1
        return False
  d[n] = 1
  return True

d = [0] * (b+1)
prime = [False] * (b+1)
for i in range(2, b+1):
  prime[i] = is_prime_num(i)
  
ans = 0
for i in range(a, b+1):
  ans += prime[d[i]]
print(ans)