[문제]
주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.
[풀이]
에라토스테네스의 체 라는 알고리즘을 이용하면 효율적으로 풀 수 있다.
주어진 숫자들의 조합 중 가장 큰 수를 구하고,
해당 수까지의 모든 수에 대해 소수 여부를 미리 판별한다. → 시간 복잡도 O(n log log n)
소수의 배수들을 다 지우는 과정을 반복한다.
처음에는 2의 배수
두번째는 3의 배수
... 이런식이다.
그러면 이를 이용해서 문제를 해결해보자.
from itertools import combinations
def solution(nums):
# 조합 중 최대합
limit = sum(sorted(nums)[-3:])
# 다이렉트 어드레스 테이블
is_prime = [True] * (limit + 1)
# 루트 limit 까지만 확인
for i in range(2, int(limit**0.5)+1):
if is_prime[i]:
# 배수 지우기
for j in range(i * i, limit + 1, i):
is_prime[j] = False
return sum(1 for combo in combinations(nums, 3) if is_prime[sum(combo)])
원래 0과 1을 False 처리해줘야 하지만 이 문제에서는 합의 최소값이 6이기 0과 1을 판별하지 않으므로 그럴 필요가 없다.