38일차. 소수 만들기

링크

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

프로그래머스

 

문제

문제 설명

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

제한사항

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

 

정답

def sosu(num):
    for i in range(2, int(num**(1/2))+1):
        if num%i==0:
            return False
    return True

def solution(nums):
    answer = 0
    hol = list(filter(lambda x:x%2==1, nums))
    chak = list(filter(lambda x:x%2==0, nums))
    for i, x in enumerate(hol):
        for j, y in enumerate(chak):
            for z in chak[j+1:]:
                if sosu(x+y+z):
                    answer+=1
        
        for j, y in enumerate(hol[i+1:]):
            for z in hol[i+j+2:]:
                if sosu(x+y+z):
                    answer+=1
    return answer

 

풀이과정

 

소수는 2를 제외하고 모두 홀수(짝수는 모두 2의 배수)이다. 그리고 1이상의 세 자연수를 합하면 반드시 1+2+3=6 이상이므로, 문제의 모든 정답은 홀수이다. 홀수는 짝수+홀수이고, 짝수는 홀수+홀수 혹은 짝수+짝수 이므로 모든 홀수에대해 짝수+짝수와 홀수+홀수의 경우의 수를 셀 것이다.

소수를 구하는 방법은 약수를 구하는방법에서 약간 비틀어서 약수가 없으면 True가 나오게 할 것이다.

def sosu(num):
    for i in range(2, int(num**(1/2))+1):
        if num%i==0:
            return False
    return True

 

먼저 짝수와 홀수만 분리한다.

    hol = list(filter(lambda x:x%2==1, nums))
    chak = list(filter(lambda x:x%2==0, nums))

그리고 모든 홀수에 대해

for i, x in enumerate(hol):

짝수+짝수의 모든 경우의수를 대입해본다.

        for j, y in enumerate(chak):
            for z in chak[j+1:]:
                if sosu(x+y+z):
                    answer+=1

만일 소수면 answer에 1을 더한다.

 

홀수+홀수도 대입해보고 소수면 1을 더한다.

        for j, y in enumerate(hol[i+1:]):
            for z in hol[i+j+2:]:
                if sosu(x+y+z):
                    answer+=1