배열 nums가 주어졌을 때, 배열에 포함된 모든 소수(prime) 요소들의 합 역시 소수인지 확인하는 문제입니다.
예를 들어 입력이 nums = [1,2,4,5,3,3]이라면, 배열 속 소수는 2, 5, 3, 3이며 이들의 합은 2+5+3+3 = 13입니다. 13 또한 소수이므로 결과는 True가 됩니다.
접근 방법
이 문제는 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하면 효율적으로 해결할 수 있습니다. 미리 일정 범위까지의 소수 여부를 모두 계산해 두면, 배열의 각 요소와 최종 합이 소수인지 빠르게 확인할 수 있습니다.
해결 절차는 다음과 같습니다.
- MAX를 10000으로 설정합니다.
- 크기가 MAX인 불리언 리스트 sieve를 만들고 모든 값을 True로 초기화합니다.
- generate_list_of_primes() 함수를 정의해 소수 테이블을 생성합니다.
- sieve[0]과 sieve[1]을 False로 설정합니다. (0과 1은 소수가 아닙니다.)
- i를 2부터 MAX-1까지 순회하면서, sieve[i]가 True인 경우 i의 제곱부터 MAX까지 i씩 증가시키며 해당 인덱스를 False로 표시합니다. (합성수 제거)
- 메인 로직에서는 다음을 수행합니다.
- generate_list_of_primes()를 호출해 소수 테이블을 준비합니다.
- total을 0으로 초기화하고, 배열을 순회하며 sieve[arr[i]]가 True인 요소만 total에 더합니다.
- 마지막으로 sieve[total]이 True이면 True를, 아니면 False를 반환합니다.
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
예제 코드
MAX = 10000
sieve = [True] * MAX
def generate_list_of_primes() :
sieve[0] = False
sieve[1] = False
for i in range(2, MAX) :
if sieve[i] :
for j in range(i * i, MAX, i) :
sieve[j] = False
def solve(arr) :
generate_list_of_primes()
total = 0
for i in range(len(arr)) :
if sieve[arr[i]] :
total += arr[i]
if sieve[total] :
return True
return False
nums = [1,2,4,5,3,3]
print(solve(nums))입력
[1,2,4,5,3,3]
출력
True
동작 원리 정리
1. 에라토스테네스의 체로 10000 미만의 모든 소수를 미리 계산해 둡니다.
2. 배열을 한 번만 순회하면서 소수인 요소들의 합을 구합니다.
3. 구한 합이 소수 테이블에서 True로 표시되어 있는지 확인해 결과를 반환합니다.
시간 복잡도
소수 체 생성에 O(MAX · log log MAX), 배열 순회에 O(n)이 소요되므로 전체 시간 복잡도는 O(MAX · log log MAX + n)입니다. 공간 복잡도는 소수 테이블 저장을 위해 O(MAX)입니다.