[lvl1]소수 만들기

출처: Programmers > Summer/Winter Coding(~2018) > 소수 만들기

문제 설명:

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

[제한사항]

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

입출력 예:

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

입출력 예 설명:

입출력 예 #1:

[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2:

[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

피드백:

소수인지 확인하는 다른 방법 : 에라토스테네스의 체
주어진 자연수 n에 대해서 1보다 크고 루트 n 이하인 모든 자연수들로 나누어떨어지지 않으면 소수

에라토스테네스의 체:

출처: Wikipedia:에라토스테네스의 체

알고리즘:

2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
자기 자신을 제외한 2의 배수를 모두 지운다.
남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
자기 자신을 제외한 3의 배수를 모두 지운다.
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
자기 자신을 제외한 5의 배수를 모두 지운다.
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
자기 자신을 제외한 7의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

그림의 경우, {\displaystyle 11^{2}>120}{\displaystyle 11^{2}>120}이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

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

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

코드 설명:

itertools의 combination 함수를 활용: 리스트에서 3가지 요소들 추출
추출한 각 tuple 형태의 요소들 sum()함수로 합쳐서 answer_list에 append
각각 소수인지 확인해서 소수일때마다 answer+=1
- 소수 확인 방법: 2부터 number-1 까지 숫자들로 나눴을때 나눠떨어지면 소수가 아님

코드:

  
from itertools import combinations
def solution(nums):
    answer = 0
    answer_list = []
    for i in list(combinations(nums, 3)):
        answer_list.append(sum(i))
    # answer_list = list(set(answer_list))

    for num in answer_list:
        for j in range(2,num):
            if (num % j) == 0:
                break
        else:
            answer+=1

    return answer

우수답변자 코드:

임의로 만든 Class를 리턴하고 채점방식이 if 리턴값==정답값 을 통해 이루어지는것을 이용하여 __eq__메소드를 재정의하여 어떤값과 비교해도 true가 나오도록 한 편법

  
class ALWAYS_CORRECT(object):
    def __eq__(self,other):
        return True

def solution(a):
    answer = ALWAYS_CORRECT()
    return answer;

우수답변자 2 코드:

  
from itertools import combinations
def prime_number(x):
    answer = 0
    for i in range(1,int(x**0.5)+1):
        if x%i==0:
            answer+=1
    return 1 if answer==1 else 0

def solution(nums):
    return sum([prime_number(sum(c)) for c in combinations(nums,3)])