거의 소수 ( 1456 번 )

1456번: 거의 소수

 

---

🧠 알고리즘

• 소수 판별(에라토스테네스의 체) + 소수 거듭제곱 생성

 

✔️ 동작 방식

• b의 제곱근까지만 에라토스테네스의 체를 돌려서 소수 목록을 구함.
• 구한 소수 리스트를 순회하면서 각 소수 p의 거듭제곱을 계산.
• 그 값이 a ~ b 범위 안에 있으면 집합(same_check)에 저장.
• 최종적으로 집합 크기를 반환 → 범위 내 “거의 소수”의 개수

---

 

🧾 코드

import sys

def _get_sosu(b):
    answer = []
    max_num = int(b ** (0.5))
    check = [True] * (max_num + 1)
    check[0], check[1] = False, False

    for i in range(2, int(max_num ** (0.5)) + 1):
        if check[i]:
            for j in range(i * i, max_num + 1, i):
                check[j] = False

    for i in range(max_num + 1):
        if check[i]:
            answer.append(i)

    return answer
    
def _main(a, b):
    sosu_list = _get_sosu(b)
    same_check = set()

    for sosu in sosu_list:
        now_num = sosu * sosu

        while True:
            if now_num > b:
                break
            if now_num >= a:
                same_check.add(now_num)
            now_num *= sosu

    return len(same_check)


a, b = map(int, sys.stdin.readline().rstrip().split())
print(_main(a, b))

---

 

⏱️ 시간 복잡도

_get_sosu(b) : 에라토스테네스의 체 ( 로그 시간 복잡도 )
for sosu in sosu_list : 소수를 순회, b의 제곱근 크기 ( 제곱근 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 제곱근 시간 복잡도 ( O(b ** (0.5)) )