프로그래머스 소수만들기(파이썬)

앞의 에라토스테네스의 체를 모르면 다른 방법으로 풀어야 한다.

소수 판별하는 다른 프로그래머스 문제에서 에라토스 테네스의 체를 보여드렸으니

이제 이를 활용해 약간의 응용문제를 해결해 보았다.

def solution(nums):
    answer = 0
    a=[1]*3001 # 인덱스가 소수면 1 아니면 0. 디폴트 값은 1
    a[0]=0  #0은 자연수가 아님
    a[1]=0  #1은 소수가 아님
    
    for i in range(2,len(a)-1):
        if a[i]==0:
            continue
        for j in range(2,len(a)//i+1):
            a[i*j]=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)):
                if a[nums[i]+nums[j]+nums[k]]==1:
                    answer+=1       #배열의 길이가 3~50이니 3중 for문도 ok
    return answer