합성수 찾기

👉 사용 언어 : PYTHON3

 

✅ Solution

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

 

👉 아이디어

• 약수가 3개 이상인 수는 일단 4~ 반복문을 돌려 체크한다.
• 해당 숫자의 제곱근까지 약수가 2개 이상 존재하면 전체 약수의 개수는 3개 이상이 된다.
  • 따라서, 제곱근까지의 약수 개수만 체크하여 합성수 여부를 알아낼 수 있다.
• 제곱근까지 약수가 2개 이상이면 정답 카운트 변수 +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

 

👉 깨달은 것 / 알게된 것

• 첫 번째 반복문에서 카운트 변수를 선언할 필요가 없었다.
• 2부터 제곱근까지 약수를 체크하여 약수가 존재하면 정답 카운트 변수 +1을 해주고 break를 걸어줌으로써, 더 효율적인 코드를 작성할 수 있다.
  • 1은 모든 수의 약수이므로 1을 제외하고 제곱근까지 약수가 존재하면 1부터 제곱근까지 약수가 최소 2개가 존재한다는 것이고 전체 약수는 최소 3개라는 뜻이므로 합성수임을 판단하고 바로 for문을 빠져나올 수 있는 것이다.