첫번째 코드

def count_measure(num):
    answer = 0
    for i in range(1,int(num**(0.5))+1):
        if i**2 == num:
            answer += 1
        elif num % i == 0:
            answer += 2
    return answer

def solution(n):
    answer = 0
    for i in range(2,n+1):
        if count_measure(i) == 2:
        	answer += 1
    return answer

부족한 점

시간 복잡도가 O(n * root(n) )이다.
근데 n이 1000000이다 보니 이것보다 더 적은 시간 복잡도를 가져야만 한다.

두번째 코드

def solution(n):
    answer = 0
    for i in range(2,n+1):
        cnt = 0
        for j in range(1,int(i**(0.5))+1):
            if cnt <= 2 and j**2 == i:
                cnt += 1
            elif cnt <= 2 and i % j == 0:
                cnt += 2
        if cnt == 2:
            answer+=1
    return answer

고친 점

if의 조건문에 조건을 빨리 끝낼 수 있도록 and 연산자의 전항을 추가했다.
그럼에도 불구하고 시간 초과와 공간 복잡도를 만족시키지 못했다.

세 번째 코드

def solution(n):
    answer = 0
    for i in range(2,n+1):
        cnt = 0
        for j in range(1,int(i**(0.5))+1):
            if cnt > 2:
                break
            if cnt <= 2 and j**2 == i:
                cnt += 1
            elif cnt <= 2 and i % j == 0:
                cnt += 2
        if cnt == 2:
            answer+=1
    return answer

고친 점

early break가 되도록 해봤지만 그래도 시간 초과가 난다.
동적 프로그래밍을 써야만 할 것 같은 느낌이 든다.

네 번째 코드

import math

def solution(n):
    arr = [True] * (n+1)
    for i in range(2,int(math.sqrt(n))+1):
        j = 2
        while i*j <= n:
            # print(i*j)
            arr[i*j] = False
            j += 1
    # print(arr)
    return sum(arr) - 2

고친 점

에라토스테네스의 체 알고리즘을 사용했다.
처음에는 해당 알고리즘이 n^2가 나오는게 아닌가 싶어서 적용하지 않았다.
그러나 적용하기 나름이었다.
핵심은 딱 루트 n까지만 탐색하는 것이다. 어차피 그 이상 넘어가는 수로 n이 나눠지지 않는다. 따라서 그 이상에서는 소수가 존재하지 않는다.
그리고 j는 커져봤자 n^(1/i)이다. 즉 내부 for문의 시간 복잡도는 n^(1/n)이므로 최종 시간 복잡도는 n^(1+1/n)이다. 따라서 시간 복잡도를 낮출 수 있었다.

어려운 문제!