1124

날짜 : 2023. 05. 11

사용 언어 : python

 

문제

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

 

 

코드

import sys
prime = [True] * 100001  # 소수면 True, 아니면 False
prime[0], prime[1] = False, False
for i in range(2, int(100001**0.5)+1):
    if prime[i]:
        idx = 2
        while idx * i < 100001:
            prime[idx*i] = False
            idx += 1


def facto(n):
    d = 2
    cnt = 0
    while n > 1:
        #print(n)
        if n % d == 0:  # 나누어 떨어지면
            n = int(n / d)
            cnt += 1
        else:
            d += 1
    if prime[cnt]:
        return 1
    else:
        return 0

a, b = map(int, sys.stdin.readline().split())
res = 0
for i in range(a, b+1):
    if prime[i]:
        continue
    res += facto(i)
print(res)

 

 

풀이

- 에라토스테네스의 체를 구현(최대값이 100,000이기 때문에 100,001까지 생성)

- 수를 입력받은 후 for문으로 탐색

- 입력받은 수가 소수일 때 / 아닐 때를 구분하면서 소인수분해 후 각 소인수의 개수에 따라 결과값을 카운트

 

 

알게된 점

- 풀었지만 TLE가 나왔고 그래서 다시 풀었다.

- 어떻게 해야 시간을 줄일까 고민한 결과 불필요하게 facto()함수에 보내지 말자는 아이디어가 떠올랐고, 소수는 무조건 소인수를 하나만 갖는다는 것이 생각났다.(ex) 17 = 1 * 17, 1은 소인수가 아님)

- 소수의 경우 소인수가 1개라는 것을 몰랐다.

- 소인수 : 주어진 자연수를 나누어 떨어뜨리는 약수 중에서 소수인 약수

 

 

참고 사이트

-