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

programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

이제 '소수'하면 바로 에라토스테네스의 체가 떠오른다.

 

1. nums의 각 원소가 1이상 1000이하이고 서로 다른 3개의 수를 고르는 것이므로 최대값이 2997이다.

   널널하게 is_prime을 3000칸 만들어두고 에라토스테네스의 체를 사용하여 소수이면 그 index를 True로, 아니면 False로 만든다.

 

2. prime = is_primes(3000)을 통해 prime배열을 is_prime배열과 똑같이 만들어준다.

 

3. 3중 반복문을 돌며 서로 다른 3개의 수를 더한 값이 소수이면 answer에 1을 더해준다. 최종적으로 answer을 출력한다.

    (prime[k]가 True라는 것은 k가 소수라는 뜻이다.)

 

def solution(nums):
    import math
    def is_primes(x):
        is_prime = [True] * x
        max_length = math.ceil(math.sqrt(x))
        for i in range(2, max_length):
            if is_prime[i]:
                for j in range(i+i, x, i):
                    is_prime[j] = False
        return is_prime

    answer = 0
    prime = is_primes(3000)
    n = len(nums)
    for i in range(n-2):
        for j in range(i+1, n-1):
            for k in range(j+1, n):
                if prime[nums[i] + nums[j] + nums[k]]:
                    answer += 1
    return answer

(프로그래머스 level: 1)

 

 

# 레벨 1이어서 그냥 브루트포스 형식으로 3중 반복문을 돌렸다.