백준 1124번: 언더프라임 Python 답안, 백준 코딩테스트 파이썬 풀이

백준 1124번: 언더프라임 파이썬 답안, 백준 코딩테스트 파이썬 풀이

문제

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

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

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

입력

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

출력

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

 

예제 입력 1 

2 10

예제 출력 1 

5

예제 입력 2 

100 105

예제 출력 2 

2

예제 입력 3 

17 17

예제 출력 3 

0

예제 입력 4 

123 456

예제 출력 4 

217

답안

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def factorize(num):
    factors = []
    i = 2
    while i * i <= num:
        if num % i == 0:
            factors.append(i)
            num //= i
        else:
            i += 1
    if num > 1:
        factors.append(num)
    return factors

def is_underprime(num):
    return is_prime(len(factorize(num)))

A, B = map(int, input().split())

count = 0
for num in range(A, B + 1):
    if is_underprime(num):
        count += 1

print(count)