[백준 1016] 제곱 ㄴㄴ수 (Python) / G1

문제

1016. 제곱 ㄴㄴ 수

코드

# n = min, m = max
n, m = map(int,input().split())
end = int(m ** 0.5)

# min~max까지의 숫자 개수
res = m - n + 1

# 방문 여부 확인
visit = [0] * (res)

# m까지 돌지 않고 m의 루트까지만 돌아도 모든 소수 판정 가능
for i in range(2, end+1):

    # 제곱의 배수를 찾기
    x = i ** 2

    # n부터 봐야하므로 해당 제곱수의 배수부터 시작하기 위한 시작점 찾기
    start = ((n-1) // x + 1) * x

    for j in range(start, m+1, x):
        if not visit[j-n]:
            res -= 1
            visit[j-n] = 1

print(res)

코드 설명

처음엔 에라토스테네스의 체를 사용한 것과 같이 리스트를 만들어서 0~max값 까지의 리스트를 순회하며 제곱수의 배수를 1로 바꿔가는 형식으로 코드를 작성하였다.
그랬더니 백준 제출 시 메모리초과가 나길래 다른 방식으로 작성을 하였다.

리스트를 만들지 않고 min~max 사이의 숫자 개수에서 제곱수의 배수가 나오면 1씩 빼주는 형식으로 구현해주었다.

시간 초과를 방지하기 위해 제곱의 배수를 찾을 때 max값까지가 아닌 max값의 루트값까지 for문을 순회하고
min값부터의 제곱수의 배수를 찾아야 하므로 for문 안에서 배수를 찾기위한 for문은
시작점을 ((n-1) // x + 1) * x로 잡아주었다.

만약 10~20 사이에서 3의 배수를 찾는다고 하면, 3의 배수는 10~20사이에서 12부터 시작을 한다.
그럼 이 12라는 숫자는 9 // 3 + 1 = 4에 3을 곱하면 12가 나온다!

한번 배수처리를 한 숫자는 처리를 그만 해줘야하므로 visit라는 리스트를 만들어서 방문여부를 확인해주었다.