합성수 찾기

문제

 

# 내 풀이

def solution(n):
    answer = 0
    count = 0
    
    for a in range(1, n+1):
        for b in range(1, a+1):
            if a%b == 0: 
                count +=1
            if count>=3:
                answer += 1
                break
        count = 0
    
    return answer

• 바깥 for 문 : n 이하의 숫자 중 합성수를 찾기 위한 for문
• 안쪽 for 문 : 각 숫자가 합성수인지 판별을 위한 for문
• 합성수 : 약수의 갯수가 3개 이상인 수
• 약수 : 어떤 수를 나누었을 때 나누어떨어지는 수, 모든 수는 기본적으로 1과 자기 자신을 약수로 갖는다.

 

# GPT 풀이

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

• for i in range(4, n + 1) : 1, 2, 3은 합성수가 될 수 없으므로 검사에서 제외
• for j in range(2, int(i**0.5) + 1) : 
  • 약수는 항상 작은 쪽과 큰 쪽이 쌍을 이룬다. 예를 들어, 12의 약수는 (1, 12) (2, 6) (3, 4) 같은 형태이다. 제곱근까지만(√12≒3.46) 검사하면 나머지는 1과 자기 자신인 수이므로 합성수가 된다.
  • 즉, i가 합성수라면 2부터 √i 중 하나로 나누어 떨어지는 경우가 반드시 존재한다.
• i % j : i가 j로 나누어떨어진다면, 합성수가 된다.

 

 

 

# i**0.5

: i에 대한 제곱근

 

 

 

 

# Math 라이브러리 방식

import math

print("2의 루트 : ", math.sqrt(2))		// 결과 : 1.4142135623730951