[프로그래머스] Lv.1 소수 만들기 - Python

https://programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

---

• 코드1

from itertools import combinations

# 소수 확인
def prime(sum):
    for i in range(2,sum):
        # 하나라도 나누어 떨어지면 소수 아님
        if not sum%i:
            return False
    # 2~(자기자신-1) 중 하나라도 나누어 떨어지지 않으면 소수
    return True
            

def solution(nums):
    answer = 0
    # 3개씩 조합으로 뽑아보자
    for three in list(combinations(nums,3)):
        # 합 구하기
        three_sum = sum(three)
        # 그 합이 소수인가?
        if prime(three_sum):
            # 맞으면 +1
            answer += 1

    return answer

 

• 생각
  • 코드1이 시간초과가 날 수도 있어서 다른 방법
    • 2 ~ (N-1)까지 확인하기에 숫자가 클 경우 시간 초과 우려
    • 수의 약수는 쌍으로 이루어져 있으므로 절반만 확인해보자
      • 예) 12의 약수는 1,2,3 / 4,6,12
      • 앞의 2,3이 나누어 떨어진다는 것을 확인하면 4,6은 확인할 필요가 없음
      • 약수의 중간 숫자를 확인하는 법은 루트!!
      • 루트12는 3.XX, int(루트12)는 3
• 코드2

from itertools import combinations

def solution(nums):
    cnt = 0
    # 3개씩 조합으로 뽑기
    for num in list(combinations(nums, 3)):
        # 합
        N = sum(num)
        
        # 소수인지 확인
        # 2~int(루트(N))까지 확인
        for i in range(2, int(N**0.5)+1):
            # 나누어 떨어지면 소수X
            if N % i == 0:
                break
        # 하나라도 나누어 떨어지지 않으면 소수
        else:
            cnt += 1
        
    return cnt