[파이썬 python] 프로그래머스 - 소수 만들기

• 소수 만들기

문제 설명

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

제한사항

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

---

입출력 예

numsresult

[1,2,3,4]	1
[1,2,7,6,4]	4

입출력 예 설명

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

---

import math

def solution(nums):
    answer = 0

    for i in range(len(nums)-2):
        for j in range(i+1, len(nums)-1):
            for k in range(j+1, len(nums)):
                total = nums[i] + nums[j] + nums[k]
                
                is_sosu = True
                for x in range(2, int(math.sqrt(total))+1):
                    if total % x == 0:
                        is_sosu = False
                        break
                
                if is_sosu == True:
                    answer += 1
    
    return answer

 

정확성  테스트
테스트 1 〉	통과 (2.57ms, 10.2MB)
테스트 2 〉	통과 (2.77ms, 10.3MB)
테스트 3 〉	통과 (0.81ms, 10.2MB)
테스트 4 〉	통과 (0.69ms, 10.3MB)
테스트 5 〉	통과 (3.62ms, 10.3MB)
테스트 6 〉	통과 (4.93ms, 10.3MB)
테스트 7 〉	통과 (0.30ms, 10.1MB)
테스트 8 〉	통과 (11.23ms, 10.3MB)
테스트 9 〉	통과 (1.16ms, 10.2MB)
테스트 10 〉	통과 (10.50ms, 10.2MB)
테스트 11 〉	통과 (0.16ms, 10.3MB)
테스트 12 〉	통과 (0.06ms, 10.4MB)
테스트 13 〉	통과 (0.18ms, 10.3MB)
테스트 14 〉	통과 (0.07ms, 10.2MB)
테스트 15 〉	통과 (0.08ms, 10.2MB)
테스트 16 〉	통과 (12.42ms, 10.3MB)
테스트 17 〉	통과 (9.88ms, 10.2MB)
테스트 18 〉	통과 (0.14ms, 10.1MB)
테스트 19 〉	통과 (0.01ms, 10.3MB)
테스트 20 〉	통과 (15.89ms, 10.2MB)
테스트 21 〉	통과 (14.99ms, 10.3MB)
테스트 22 〉	통과 (2.58ms, 10.1MB)
테스트 23 〉	통과 (0.01ms, 10.2MB)
테스트 24 〉	통과 (12.45ms, 10.2MB)
테스트 25 〉	통과 (11.73ms, 10.3MB)
테스트 26 〉	통과 (0.01ms, 10.3MB)

 

후기

 수학에 약해서 효율적으로 소수를 구할 방법을 검색해봤다. 숫자를 제곱근하고, 처음부터 제곱근한 값까지 나누어 떨어지는 것이 있다면 소수가 아니라고 한다.

 

풀이

(1) for문을 3개씩 돌려 총합 값을 찾는다.

(2) 총합 값을 토대로 소수인지 아닌지를 확인한다. 소수는 1과 자기자신만 가능한 수이므로, 2부터 자기자신을 제곱근 한 수까지 탐색하여, 나누어 떨어지면 소수가 아닌 것으로 알 수 있다.