[1016] 제곱 ㄴㄴ 수(제곱으로 나누어떨어지지 않는 수)

1016번: 제곱 ㄴㄴ 수

 

분석

min ≤ max ≤ min + 1,000,000 : 일반적인 반복문으로 구하면 시간초과

1. 범위 A~B사이 pow(정수 제곱수)로 떨어지는 수 구함 ➔ checkList[ (A/제곱수 ~ B/제곱수)*제곱수-A]=True 
2. Fase 개수 출력

1. 제곱수인 4

0	1	2	3	4	5	6	7	8	9
1	2	3	4	5	6	7	8	9	10

j=1 : (4*1)-1=3 (3번 인덱스 제곱수 True)
j=2 : (4*2)-1=7 (7번 인덱스 제곱수 True)
j=2 : j*제곱수가 max(10)을 넘어서 종료

2. 제곱수 9

0	1	2	3	4	5	6	7	8	9
1	2	3	4	5	6	7	8	9	10

j=1 : (9*1)-1=8 (8번 인덱스 제곱수 True)
j=2 : j*제곱수가 max(10)을 넘어서 종료

 

풀이

"""
어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다.
제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.
1 ≤ min ≤ 1,000,000,000,000
min ≤ max ≤ min + 1,000,000
"""
import math
min,max=map(int, input().split())
checkList=[False]*(max-min+1)

for i in range(2, int(math.sqrt(max)+1)):
    pow=i*i  # 제곱수
    startIdx=int(min/pow)
    if min%pow!=0:
        startIdx+=1
    for j in range(startIdx,int(max/pow)+1):
        checkList[int(j*pow-min)]=True

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