[백준 1124번] 언더프라임 - 파이썬

https://www.acmicpc.net/problem/1697

💡문제 분석 요약

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

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

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

💡알고리즘 설계

2부터 B+1 까지, 해당 숫자가 소수인지와 소수의 목록 길이를 배열에 저장한다.

만약 이 소수의 목록 길이가 소수일 경우, answer에 1을 더한다.

마지막에 answer의 크기를 출력한다.

 

int(n**0.5)+1인 이유: N의 약수는 무조건 루트N 안에 위치함.

💡코드

import sys
input = sys.stdin.readline

def is_prime(n):
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            DP[n]=DP[n//i]+1
            return False
    DP[n]=1
    return True  

A, B=map(int, input().split())
DP=[0 for _ in range(B+1)]
is_prime_DP=[False for _ in range(B+1)]
answer=0

for i in range(2, B+1):
    is_prime_DP[i] = is_prime(i)

for i in range(A, B+1):
    if is_prime_DP[DP[i]]:
        answer+=1

print(answer)

 

💡 느낀점 or 기억할 정보

처음에는 재귀를 이용해 소수의 목록 길이를 구하다가, 매 숫자마다 소수 여부를 판단하려니 시간이 너무 오래 걸려서 DP로 저장했다.