[프로그래머스/Programmers] Summer/winter Coding(~2018) 소수 만들기 (파이썬 Python)

문제

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

프로그래머스

 

제출 코드

- 소수 구하기는 좀 흔한 문제여서 풀이 방법(?)을 외워두면 좋은 것 같다.

- 그냥 기출 문제 풀 듯 풀었다.

- 소수 판별 추가 설명

•  num**0.5는 주어진 숫자 num의 제곱근을 의미
• 제곱근을 사용하는 이유는 소수를 판별하는데 있어서 효율성을 높이기 위해서.
• 소수를 판별할 때는 해당 숫자의 제곱근까지만 검사하면 됨. 왜냐하면 제곱근 이상의 수로 나누어 떨어지는 경우가 발생할 수 없기 때문.

 

•  만약 어떤 수 num이 소수가 아니라면, 그 수는 반드시 제곱근보다 작거나 같은 다른 소수로 나누어진다.
• 그래서 range(2, int(num**0.5) + 1)에서는 2부터 num의 제곱근까지의 범위만 검사하면 충분.
• 만약 이 범위 내에서 num을 나누는 어떤 소수도 발견되지 않는다면 num은 소수임이 확실

 

<예> 16이라는 숫자가 주어졌을 때 이 숫자가 소수인지를 판별

• 16은 소수가 아님.
• 왜냐하면 16을 나누는 소수로 1, 2, 4, 8, 16이 있다.
• 여기서 16의 제곱근은 4.
• 만약 16이 소수였다면 4보다 큰 다른 어떤 수로도 나누어 떨어지지 않았어야 했음.
• 하지만 이미 2, 4에서 나누어 떨어지므로 16은 소수가 아님.
• 제곱근인 4까지만 검사했는데도 결과가 나왔음 => 효율적

def is_prime(num) :
    if num < 2:
        return False
        # 해당 숫자의 제곱근까지 검사.
    for i in range(2, int(pow(num, 0.5)) + 1):
        if num % i == 0:
            return False
    
    return True

def solution(nums):
    answer = 0

    # nums 에 들어있는 숫자의 개수
    nums_n = len(nums)
    
    # 세 개의 숫자를 골라 합함.
    for i in range(nums_n):
        for j in range(i+1, nums_n):
            for k in range(j+1, nums_n):
                num_sum = nums[i] + nums[j] + nums[k]
                if is_prime(num_sum) :
                    answer += 1

    return answer

 

채점 결과