[Coding Test] 1016번 : 제곱 ㄴㄴ 수

백준 코딩테스트 1016번 : 제곱 ㄴㄴ 수

문제 설명

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

문제 풀이

• a,b를 정수로 정의하여 받아옴
• 제곱ㄴㄴ수를 세어줄 count 정의
• 반복문을 통해 max 수를 범위로 반복
• 반복문 안의 조건문을 이용해 제곱ㄴㄴ수를 구함
• 수가 1일 경우는 항상 제곱ㄴㄴ수 이기 때문에 count에 1을 더해줌
• math의 sqrt 함수를 이용해 제곱근이 정수이면 제곱수인 것이기 때문에 continue
  [기초문법] math : sqrt(), pow() 함수
• 아닐 경우, 제곱ㄴㄴ수 이므로 count에 1을 더해줌
• 최종적으로 나온 count를 출력

처음 코드

import sys
import math

a, b = sys.stdin.readline().split()
a = int(a)
b = int(b)
count = 0

for i in range(b):
    if i == 1:
        count += 1
    elif math.sqrt(i).is_integer():
        continue
    else:
        count += 1

print(count)

• 시간초과

• 코드에 오류는 없었지만 시간초과로 인해 백준문제를 통과하지 못함

• 에라토스테네스의 체 를 이용하여 풀면 시간복잡도가 현저히 줄어준다고 하였지만, 정확하게 이해하지 못해 우선 통과하지 못한 코드로 올림

• 에라토스테네스의 체 : 고대 그리스 수학자가 만들어 낸 소수를 찾는 방법

• 수가 1조 이상으로 올라 간다는 것을 고려해 에라토스테네스의 체를 응용하여 시간 복잡도를 줄여줌

* 이 문제는 백준 코딩테스트 1016번 문제입니다.