[BOJ]1016. 제곱ㄴㄴ수

문제:

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱 ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱 ㄴㄴ수가 몇 개 있는지 출력한다.

입력:

첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000.000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 [min,max]구간에 제곱ㄴㄴ 수가 몇 개인지 출력한다.

풀이방법:

어떤 수 X가 한 제곱수로 나누어지는지 확인하는 것 보다 제곱수가 나누어 떨어지게 만들 수 있는 수들을 지워나가는 것이 시간복잡도를 줄일 수 있다.(에라토스테네스의 체와 비슷)

check=[0]*1000001
a,b=map(int,input().split())
for i in range(2,b):
    if i*i > b:
        break
    start=i*i-a%(i*i)
    if start == i*i:
        start = 0
    for j in range(start,b-a+1,i*i):
        check[j]=1
ans=0
for i in range(b-a+1):
    if check[i]==0:
        ans+=1
print(ans)

문제링크:

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