1124번: 언더프라임 (acmicpc.net)

##
소인수분해를 했을때, 그 소수 목록의 개수가(중복포함) 소수인 숫자 찾기

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

# 소수판별
def is_prime(n):
    if n == 1: return False
    for i in range(2,int(n**(0.5)+1)):
        if n % i == 0:
            return False
    return True

# 소인수분해 하고 언더프라임 확인
def is_under_prime(n):
    div_l = []
   
    start_num = 2
    while (n != 1):
        if n % start_num == 0:
            n = n // start_num
            div_l.append(start_num)            
        else:
            start_num += 1
            while (is_prime(start_num) == False):
                start_num += 1
    #print(div_l)
   
    return is_prime(len(div_l))
   
   
c = 0
for tmp in range(A,B+1):
    if is_under_prime(tmp):
        c += 1
print(c)
시간초과난다
일일이 소수인지 판별하는 과정이 문제로 보인다


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

# 에라토스테네스의 체
def erat(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for i in range(p * p, n+1, p):
                # 왜 p*p인가?? - p가 소수라면 그 배수들은 이미 이전단계에서 제거되었다.
                # p를 기준으로 가장 작은 배수는 p*p고, 이전의 배수는 따질 필요 없다.
                is_prime[i] = False
        p += 1
    return [i for i, prime in enumerate(is_prime) if prime]

primes = erat(B)

# 소인수분해 하고 언더프라임 확인
def is_under_prime(n):
    div_l = []
   
    i = 0
    while (n != 1):
        if n % primes[i] == 0:
            n = n // primes[i]
            div_l.append(primes[i])            
        else:
            i += 1
    #print(div_l)
   
    return len(div_l) in primes
   
   
c = 0
for tmp in range(A,B+1):
    if is_under_prime(tmp):
        c += 1
print(c)
정답낸거


# 에라토스테네스의 체
def erat(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for i in range(p * p, n+1, p):
                # 왜 p*p인가?? - p가 소수라면 그 배수들은 이미 이전단계에서 제거되었다.
                # p를 기준으로 가장 작은 배수는 p*p고, 이전의 배수는 따질 필요 없다.
                is_prime[i] = False
        p += 1
    return [i for i, prime in enumerate(is_prime) if prime]