[프로그래머스 level1] 소수 만들기 - 파이썬

소수 만들기

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

---

입출력 예

numsresult

[1,2,3,4]	1
[1,2,7,6,4]	4

 

나의 코드

# 에로토스테네스의 체
def prime_list(N):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * (N + 1)

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int((N + 1) ** 0.5)

    for i in range(2, m + 1):
        if sieve[i] == True:  # i가 소수인 경우
            for j in range(i + i, N + 1, i):  # i이후 i의 배수들을 False로 판정
                sieve[j] = False

    return [i for i in range(2, N + 1) if sieve[i] == True]


def solution(nums):
    sosulist = prime_list(3000)
    sumlist = []
    answer = 0
    for i in range(len(nums) - 1):
        for j in range(i + 1, len(nums)):
            for k in range(j + 1, len(nums)):
                sumlist.append(nums[i] + nums[j] + nums[k])

    for q in sumlist:
        if q in sosulist:
            answer += 1

    return answer

1. 3개를 합쳐 소수를 만들어야 하기 때문에 처음에 투 포인터를 하려 했다가 이건 아닌 것 같고 그냥 for문 3번 돌리면 된다

2. 소수인지 판별하기 위해 에라토스테네스의 체를 이용하였다. 크기는 nums의 원소가 최대 1000이라고 해서 최대 3000을 잡았다

 

시간 오래걸릴것 같아서 안될 줄 알았는데 돼서 이상하다