[프로그래머스] - 소수만들기

프로그래머스 - 소수 만들기

조합과 에라토스테네스의 체를 알고있다면 간단히 풀리는 문제
근데 그런 문제치고 조금 해맸는데 문제를 제대로 안읽었다.

1. 3개의 자연수를 더하는데 자연수의 범위가 1000이므로 최대 3000의 값이 나올 수 있음 (처음에 1000까지만 확인함)
2. 에라토스테네스의 체를 사용할 때 최댓값의 최곱근 까지의 범위만 찾아도 된다. (기억해두기)

- 에라토스 테네스의 체 : n범위 이내의 소수를 구할 수 있다. 
    - 시간복잡도 : nlogn (n=1,000,000이하면 무리없이 가능) 
    - 구현 
     1. 최대범위를 구하고 최대범위만큼 전부 True인 리스트생성
     2. 0과 1은 소수이고 곱했을 때 의미가 없기 때문에 2부터
     3. 2 ~ n**.5 만큼 순회하면서 prime_list[i]가 True면
       소수임을 인지하고 j=2 초기화 후 i*j가 n+1보다 커질 때
       까지 리스트[i*j]를 전부 False로 만든다. 
     4. j+=1로 올려가며 소수가 아닌 것들을 전부 False로
     5. list comprehension으로 True인 것들을 전부 저장

from itertools import combinations as Combi

def solution(nums):
    n = 3001
    prime_list = [True]*(n+1)
    for i in range(2,n+1):
        if prime_list[i] == True:
            j=2
            while j*i < n+1:
                prime_list[i*j] = False
                j+=1

    prime_num = [i for i in range(n+1) if prime_list[i]]

    answer=0
    # [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    for value in Combi(nums,3):
        if  sum(value) in prime_num :
            answer+=1


    return answer