[코테] 제곱ㄴㄴ수

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

1016번: 제곱 ㄴㄴ 수

문제설명:

주어진 범위 내에서 1보다 큰 수들의 제곱수로 나누어 떨어지지 않는 숫자의 개수를 구하여라.

 

소요시간:

30분

 

난이도:

골드1

 

제출횟수:

1회

 

코드:

m, M = map(int,input().split())
arr = [0]*(M-m+1)
i = 2
while (d:=i**2)<=M:
    #제곱근중 가장작은것이 Max을 넘어가지 않는다면
    j = m//(d)
    #min을 i로 나눈 몫 부터 시작함(그전에는 굳이 할당 x)
    if m%(d)==0:
        #나누어떨어진다면 
        arr[m-m] = 1
    
    for k in range(j+1,M//d+1):
        #k는 몫
        arr[d*k-m] = 1
    i+=1
    
print(arr.count(0))

먼저 문제를 보고 에라토스 테네스의 체 가 먼저 떠올랐고, 이를 위해 배열을 할당해주려 하는데, 범위를 살펴보았을때 min과 의 범위는 매우 큰데, min과 max의 차이는 크지 않았습니다. 이에 전체다 배열을 할당하면 안되고 그 차이만큼만 할당해 주어야 겠다고 생각했습니다.(실제로도 min보다 작은값은 어차피 취급을 하지 않기 때문에 범위가 크지 않더라도 할당해줄 이유는 없음) 그래서 그 차이만큼만 할당을 해준 뒤, 2부터 시작을 해주었고, 예를들어 min이 10만이라고 가정했을때 사실 2의 제곱수인 4의 배수중에서 4부터 10만 까지의 값은 필요없고 10만부터 우리가 필요한 값들이기 때문에 처음부터 세지않고 min에서 제곱수를 나눈뒤 그 몫부터 시작하였습니다. 다만 이때 딱 나누어 떨어지는 경우를 제외한다면 몫에 제곱수를 곱한값이 min보다 작을것 이기 때문에 +1 을 해주어 k를 시작하고 딱 나누어 떨어지는 경우라면 따로 따로 처리를 해주었습니다. 최대값은 어차피 포함이기 떄문에 딱 나누어 떨어저도 상관없기에 M//d+1을 해주었고, 이렇게 1을 해준것이 나누어 떨어진다는 뜻이기  때문에 0의 개수를 세어 출력해주었습니다.