주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.
입출력 예 #1[1,2,4]를 이용해서 7을 만들 수 있습니다.
입출력 예 #2[1,2,4]를 이용해서 7을 만들 수 있습니다.[1,4,6]을 이용해서 11을 만들 수 있습니다.[2,4,7]을 이용해서 13을 만들 수 있습니다.[4,6,7]을 이용해서 17을 만들 수 있습니다.
저번에는 약수 만들기에 관한 문제였다면 이번에는 소수 판별 문제이다.
가장 간단한 방법으로 소수 판별을 하였는데, 다음과 같다. n이 소수인지 판별하기 위해 2 ~ n-1까지 나누어 보고 나머지가 0이 아닌 것이 하나라도 있다면 소수가 아니다. 따라서, boolean 변수를 True로 하고 나머지가 0이 나오면 False로 바꾸고, break! 해주면 된다. 보통, 2 3 5 7 선에서 해결되므로..? break해주면 그나마 빨리 끝날 것으로 예상된다.
이것보다 효율적인 방법은 '에라토스테네스의 체'가 있다. 소수 판정법 중에 자연수 n에 대해서 n-1까지 가지 않고, 루트 n까지만 가도 된다. ( 2≤ q ≤sqrt(n) )
def solution(nums):
answer = 0
n = len(nums)
tmp = 0
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
tmp = nums[i] + nums[j] + nums[k]
result = True
for x in range(2, tmp):
if tmp % x == 0:
result = False
break
if result:
answer += 1
return answer