백준 1016 제곱ㄴㄴ 수

문제

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

입력

첫째 줄에 두 정수 min과 max가 주어진다.

출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

제한

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

 

예제 입력 1

1 10

예제 출력 1

7

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

1016번: 제곱 ㄴㄴ 수

문제 접근

첫 풀이는 전에 풀었던 소수와 관련된 문제를 풀었던 것과 마찬가지로 간단하게 범위에 해당하는 수마다 2부터 해당 수까지 제곱수에 나누어떨어지는지 확인하였다

mi, ma = map(int,input().split())
count = 0
for i in range(mi,ma+1):
  isnnum = 1
  for j in range(1,i):
    squared = j * j
    if squared == 1:
      pass
    elif i % squared == 0:
      isnnum = 0
  if isnnum == 1:
    count += 1
print(count)

그러나 min과 max의 범위가 결코 작지 않았고 생각보다 꽤 커서 그 다음에 생각한 방법이 에라토스테네스의 체였다. 하지만 이를 구현하려고 해도 시간 복잡도를 줄이는 방법을 떠오르는게 쉽지 않았고 다른 코드를 참고해서 보았지만 직관적이지 않았다. 그럼에도 불구하고 상당히 간단한 코드로 표현하여 다음과 같은 코드를 사용했다.

mi, ma = map(int,input().split())
squared = [i**2 for i in range(2,int(ma**0.5)+1)]
print(squared)
num = [1] * (ma-mi+1)
for i in squared:
  n = mi //i*i #n이 탐색하는 제곱수이다.
  while(n < ma +1):
    if n - mi >= 0:#당연히 제곱수가 mi의 범위에 포함이 되어야 한다
      num[n-mi] = 0 #num 리스트가 min부터 max까지기에 n-mi를 해야 제곱ㄴㄴ수 추적
    n += i #제곱수만큼 더하여 추적이 가능하다 
print(sum(num))