[백준]1016 제곱ㄴㄴ수 #에라토스테네스의 체 응용

1. 풀이

에라토스테네스의 체를 풀 때 처럼 처음에 검사할 숫자만큼 배열을 만들고 제곱 ㅇㅇ수를 삭제하는 식으로 문제를 해결하면된다.

이때 수의 크기 자체는 크고(1,000,000,000,000), min과 max사이의 차이(1,000,000)는 작기때문에 검사를 1부터 하는게 아니라 min부터 한다. 

ex)

min=1001, max=5015 일때

isNoNo=[1,1,1,1....1] (길이는  5015-1001+1) 배열을 만든다.

 

(1) 이후 가장 작은 제곱수인 4(=2^2)부터 차례대로 탐색. 이때 1부터가 아닌 min에 가장 가까운수부터 탐색. (=1004)

제곱수	제곱 ㅇㅇ수
4	1004	1008	1012	1016	1020	1024	1028	...	5012

(2) 그 다음 가장 작은 제곱수 9(=3^2)를 검사하면

제곱수	제곱 ㅇㅇ수
4	1004	1008	1012	1016	1020	1024	1028	...	5012
9	1008	1017	1026	1035	1044	...	5013

.

.

.

(3) 이렇게 나눌 수 있는 가장 작은 큰 제곱수인 70까지 나눈다

제곱수	제곱 ㅇㅇ수
4	1004	1008	1012	1016	1020	1024	1028	...	5012
9	1008	1017	1026	1035	1044	...	5013
...	...	...	...
70	4900

즉 1001~5015에서 위에서 찾은 제곱ㅇㅇ수를 모두 빼주면 된다.

2. 주의

(1) 시간복잡도가 2중포문에 최대만 계산하면 sqrt(1,000,000,000,000) * (1,000,000/4) 라서 시간이 초과할것 같지만, 제곱으로 증가하며 제곱수당 제곱ㅇㅇ수가 급격히 감소하며 시간내로 들어오는거같음.

(2) 소수를 구할 때 에라토스테네스의 체는 약수중 가장 작은 값들을 검사하기 때문에 소수가 아닌 수는 포문이 돌지 않는데, 이 문제에서는 소수를 검사하는것이 아니기 때문에 모든 포문을 다 돌어야 한다

 

3. 소스코드

import math

min,max=map(int,input().split())
sqrtMax=int(math.sqrt(max))+1
isNoNo=[1 for i in range(max-min+1)]

for i in range(2,sqrtMax):
    double=i**2

    start=math.ceil(min/double) #몫
    fin=(max//double)+1

    for j in range(start,fin):
        isNoNo[j*double-min]=0

#print(isNoNo)
print(sum(isNoNo))