BOJ1016 제곱 ㄴㄴ수

문제

BOJ1016 제곱 ㄴㄴ수
골드1 | 백준 1016 | Python3 파이썬 풀이

알고리즘

1. 입력 받음
2. 에라토스테네스 체를 기록하기 위한 리스트 생성 (N ~ M + 1)
3. 1부터 제곱 수가 MAX보다 작을 때까지 반복 (인덱스 변수 i)
4. j는 배수 만들기 용 변수 (i * i * j가 MAX보다 작을 때까지 반복)
5. i * i * j가 인덱스 범위 내이면 방문 체크, 개수 세기
6. 반복 종료 후 전체 개수에서 방문하지 않은 곳의 수를 출력 (len(a) - count)

문제점
1) 에라토스테네스의 체를 이용하지 않으면 → 시간 초과
2) 에라토스테네스의 체를 이용하고 → 숫자를 담는 리스트를 만들거나, 리스트의 길이를 0부터 MAX까지 하면 메모리 초과
3) 하나의 리스트를 이용해 에라토스테네스의 체를 이용해야 함
4) 방문 체크를 해야 하는데, 인덱스 범위 조정 필요 및 체크 필요 (N ~ M + 1)

→ 범위를 조정하지 않으면 시간 초과

5) C 계열은 int 범위를 벗어나므로 long long 타입 사용

코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

# 에라토스테네스의 체 (소수면 True)
a = [True for _ in range(M - N + 1)]
count = 0
i = 1

# 에라토스테네스의 체
while i * i <= M:
    i += 1
    j = N // (i * i)
	
    while i * i * j <= M:
    	# i^2의 배수
        sq = i * i * j
			
        if sq >= N:
            if a[sq - N]:
                count += 1
                # 소수가 아니므로 체크
                a[sq - N] = False
        j += 1

print(len(a) - count)

결과

기본 아이디어는 쉬우나 (에라토스네테스의 체 응용)
시간 초과와 메모리 초과를 줄이기 위해, 인덱스 범위를 재조정하는 것이 어려웠음

→ 더 빠르고 메모리 소모가 적은 밀러-라빈 방식 사용해보기