[백준] #13909

처음 푼 코드

import sys
input = sys.stdin.readline

N = int(input())
lst = []

def divisor(n):
    divisors = set()
    for i in range(1, n+1):
        if n % i == 0:
            divisors.add(i)
    return len(divisors)

for i in range(1, N+1):
    if divisor(i)%2 == 0:
        lst.append(0)
    else: lst.append(1)
    
print(lst.count(1))

반복문의 향연, 시간복잡도는 O(N^2)
그런데 문제에서 요구하는 N의 수는

코드 짜면서도 시간초과 날 줄 알았음.

가만히 생각해보니, 약수의 개수가 홀수인 수: 제곱수...

print(int(input())**0.5)