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

합성수 찾기

 

문제 설명

약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 n이 매개변수로 주어질 때 n이하의 합성수의 개수를 return하도록 solution 함수를 완성해주세요.

 

제한사항

• 1 ≤ n ≤ 100

입출력 예 설명

입출력 예 #1

• 10 이하 합성수는 4, 6, 8, 9, 10 로 5개입니다. 따라서 5를 return합니다.

입출력 예 #1

• 15 이하 합성수는 4, 6, 8, 9, 10, 12, 14, 15 로 8개입니다. 따라서 8을 return합니다.

 

 

내가 작성한 코드

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

-> 처음에 문제를 잘못읽고 3'초과'로 해서 지피티의 도움을 받음 .. / 분명히 맞는것 같아서..돌렸는데.. 별거아니었다니 문제와 코드 꼼꼼히 확인하기!

 

 

 

 

다른 사람이 작성한 코드

def solution(n):
    output = 0
    for i in range(4, n + 1): # 4부터 시작 (1~3은 무시)
        for j in range(2, int(i ** 0.5) + 1): # j는 최대 √i까지만 체크
            if i % j == 0:
                output += 1
                break
    return output

=> 시간복잡도가 O(n√n)로 더 좋은 코드!라고 한다! 제곱근과 정수를 응용해서 그것을 제외한 나머지의 약수를 찾는다는 부분이 매우 놀라운 코드.. 생각도 못했네요..

 

• TaciTa 의 답변 :  i까지로 하면 컴파일 시간이 너무 길어지기 때문입니다! 반복 범위를 줄이기 위해, 대부분 자연수의 약수는 대상의 제곱근 이하의 약수 하나와 이상의 약수 하나씩 한 쌍을 이룬다는 점을 응용해 i의 제곱근까지 반복하게 한 다음, 4나 9등의 제곱수를 고려해 +1을 해서 예외를 해결한 경우입니다!

 

 

GPT가 작성한 코드(참고)

def solution(n):
    # 0과 1은 소수가 아님
    is_prime = [False, False] + [True] * (n - 1)

    # 에라토스테네스의 체로 소수 판별
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False

    # 소수 개수 구하기
    prime_count = sum(is_prime)
    
    # 합성수 개수 = (2~n까지 총 개수) - 소수 개수
    composite_count = (n - 1) - prime_count
    return composite_count

 

=> 더 좋은 성능을 가진 시간복잡도를 찾은 김에 지피티에게 시간복잡도를 더 줄여달라고 해봤다! 에라토스테네스 방식이란 것을 알려주었다! 아... 지금 봤더니 에라토스테네스 방식도 윗 분과 같이 소수판별식을 저런식으로 구현했구나. 이걸 알고있었더라면 저렇게 풀고있었겠네! 이 개념 참고!!

 

• 소수만 걸러서 전체 수 - 소수 개수로 합성수 구함.
• 시간복잡도: O(n log log n) → 사실상 가장 빠른 소수 판별 알고리즘
• n이 작으면 차이 없음 (n < 10,000)
• n이 크면 (10⁵ 이상) → 에라토스테네스 압승

 

 

 

 

에라토스테네스 방식

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 만든 소수를 빠르게 구하는 알고리즘

2부터 n까지의 자연수 중에서 소수만 남기고, 나머지(=합성수)는 지워나가는 방식

1. 2부터 n까지 모든 수를 적어
2. 2는 소수니까 남기고, 2의 배수를 지워
3. 남은 수 중 다음 수(3)는 소수, 3의 배수를 지워
4. 다음 남은 수(5)도 소수, 5의 배수를 지워
5. … 이 과정을 √n까지 반복하면
6. 지워지지 않고 남은 수가 모두 소수야!

합성수 판별, 소수 개수 구하기, 빠른 소수 테이블 생성, 수학 문제, 암호학, 알고리즘 대회 등에서 자주 등장!

O(n log log n) → 매우 빠름!

 

 

 

 

 

 

 

 

회고

시간복잡도를 참고해서 구현을 하는 것이 좋을 것 같다. 하지만 지금은 코드를 구현한다는 점부터 우선이기때문에 시간복잡도에 대한 것은 오답을 정리하며 하나씩 배워서 적용해 나아가면 된다.