[프로그래머스] 합성수 찾기

난이도 : 코딩테스트 입문 (Lv.0) 

정답률 : 85%

문제 : [프로그래머스] 합성수 찾기

 

 

< 나의 풀이 >

def solution(n):
    answer = 0
    for i in range(4, n+1):
        cnt = 0
        for j in range(1, i+1):
            if i%j == 0:
                cnt += 1
        if cnt >= 3:
            answer += 1
    return answer

▶ 우선 합성수는 4부터 시작한다.

    (1, 2, 3의 경우는 약수가 1과 자신 뿐이기 때문에 총 2개 존재하기 때문이다.)

    따라서 4부터 n까지 기본 범위를 설정 한 후 (for i in range(4, n+1))

    해당하는 값 (i)의 약수의 개수(cnt)를 구해준다. 

    구한 개수의 값이 3 이상인 경우 답을 체크해준다. (answer += 1)

    

 

< 다른 사람의 풀이 >

def solution(n):
    output = 0
    for i in range(4, n + 1):
        for j in range(2, int(i ** 0.5) + 1):
            if i % j == 0:
                output += 1
                break
    return output

▶똑같이 합성수는 4 이상부터 시작하지만 

    약수의 개수를 세줄 때 제곱근까지만 해준다. 

    (약수는 대칭으로 이루어져있기 때문에 N**0.5 * N**0.5 = N으로 가운데 값은 제곱근임을 알 수 있다.)

    또한, 1과 자기 자신 그 외의 단 한 개의 약수만 존재해도 3개 이상인 합성수이므로

    꼭 필요한 경우만 카운팅해주기 때문에 코드가 효율적이다.

 

 

같은 문제라도 필요한 값들만 카운팅하면 시간적으로 효율을 얻을 수 있기 때문에 참고하면 좋을 것 같다~