프로그래머스 lv0 합성수 찾기

1. 합성수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/120846

2. 완전탐색 풀이

# 에로토스테네스의 체
def solution(n):
    DB = [0]*101
    answer = 0
    
    for i in range(2, n+1):
        if DB[i] == 1:
            continue
        DB[i] = 1
        
        for ni in range(i, n+1, i):
            if DB[ni] == 1:
                continue
            DB[ni] = 1
            answer += 1
    
    return answer

# 제곱근 계산법
def solution(n):
    answer = 0
    
    for i in range(2, n+1):
        for d in range(2, int(i**0.5)+1):
            if i%d == 0:
                answer += 1
                break
    return answer