소수 만들기 (python)

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

프로그래머스

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

---

code

# Lv.1
# 소수 만들기
from itertools import combinations
def solution(nums):
    count = 0
    for i in combinations(nums, 3):
        count += is_prime(sum(i))
    return count

def is_prime(num):
    if num == 0 or num == 1:
        return 0
    else:
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return 0
        return 1

https://github.com/soaringwave/Python-algorithm-studying/blob/main/programmers/Lv.1/pick_three_sum_prime.py

 

알고리즘

def is_prime(num):
    if num == 0 or num == 1:
        return 0
    else:
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return 0
        return 1

정수 num이 소수인지 확인해서 맞다면 1을 아니라면 0을 반환하는 is_prime 함수를 만든다. 0, 1은 소수가 아니기에 바로 0을 반환한다. 나머지 수는 해당 수의 제곱근을 정수로 만들어 1을 더한 값까지 0으로 나누어 떨어지는 수가 있는지 확인한다(반복문의 범위를 줄이고자). 여기까지 0을 리턴하지 않았다면 소수이기 때문에 1을 리턴한다.

 

from itertools import combinations
def solution(nums):
    count = 0
    for i in combinations(nums, 3):
        count += is_prime(sum(i))
    return count

combination을 이용해 nums의 원소 중 3개가 원소인 배열을 만든 후, 그 세 원소의 합이 소수인지 is_prime 함수를 통해 확인한다. count에 함수의 반환값을 더해서 답으로 반환한다.

 

피드백

소수인지 확인할 때 반복문의 범위를 range(2, (num // 2) + 1)로 해도 된다. 그러나 range(2, int(num ** 0.5) + 1)가 더 효과적이다.

https://github.com/soaringwave/Python-algorithm-studying/commit/1a83e5685f462eea81d3fcbade143917a7bf7060