[백준] 1016. 제곱 ㄴㄴ 수

문제

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




풀이

전형적인 에라토스테네스의 체 문제이다. 범위가 1000000000000 ~ 1000001000000 를 가지므로 min부터 max 까지 돌린다면 O(n^2)의 시간이 걸린다. 따라서 좀 더 최적화된 방법이 필요하다.
min 이상인 수 중에 가장 작은 제곱수를 찾고 max 이하까지의 범위를 전부 찾고, 그걸 1 * 1 부터 n * n의 범위까지 전부 돌려 찾으면 시간 안에 찾을 수 있다.
파이썬은 거의 처음과 다름이 없어서 C++처럼 능숙하게 다루지 못한다. 원래 부딪히면서 익히는 본인의 특성상 무작정 코딩하면서 공부했던걸 주석으로 달았다.

# 파이썬은 a = input() b = input() 이런식으로 입력을 넣으면 입력을 넣을 때 '1 10' 과 같이 한줄에
# 입력을 전부 넣지 못한다. 따라서 입력 받을 변수를 map에 넣고 split으로 공백 단위로 잘라서 입력을
# 시켜주면 된다.
min, max = map(int, input().split(' '))
# 파이썬은 기본적으로 가변길이의 배열 및 리스트를 가진다. 따라서 고정길이를 가지려면 배열에 초기화 값을 넣고
# 할당하고자 하는 크기를 곱해준다.
num = [0] * 1000001

# 제곱ㄴㄴ수는 2이상인 제곱수로 나누어지지 않은 수를 의미하므로 2부터 시작한다.
n = 2
while n * n <= max:
    tmp = n * n
    n += 1

# 최소값이 n * n으로 나누어지지 않은 제곱ㄴㄴ수이면 시작점을 min으로 해준다.
    if min % tmp == 0:
        start = min
# 그게 아니면 min에 n * n으로 나눈 나머지를 빼서 n * n의 배수로 만들어주고 빼주게 되면 min보다 작아지므로 n * n을 다시 더해준다.
    else:
        start = min - (min % tmp) + tmp

    m = 0
# n * n의 배수꼴로 나오면 max 이하까지 n * n을 더하면서 체크해준다 
    while start + tmp * m <= max:
        #print(start * m - min)
        num[start + tmp * m - min] = 1
        m += 1


cnt = 0
for i in range(0, max - min + 1):
    #print(i + 1, num[i])
    if num[i] == 1:
        cnt += 1


print(max - min + 1 - cnt)