소수 만들기

링크 : https://programmers.co.kr/learn/courses/30/lessons/12977

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

(프로그래머스 > 코딩테스트 연습 > Summer/Winter Coding(~2018) > 소수만들기(level1))

 

---

 

<문제>

 

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

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

 

---

 

<내가 작성한 코드>

 

import itertools
def solution(nums):
    group = list(itertools.combinations(nums,3))
    add = []
    for item in group:
        add.append(sum(item))

    prime_number = [True] * (max(add)+1)
    m = int(max(add)**0.5)
    for i in range(2, m+1):
        if(prime_number[i]==True):
            for j in range(i+i, max(add)+1, i):
                prime_number[j] = False

    answer =0
    for item in add:
        if(item!=0 and item!=1 and prime_number[item]==True):
            answer+=1
    return answer

 

import itertools
def solution(nums):
    answer = 0
    for item in itertools.combinations(nums,3):
        s = sum(item)
        flag = True
        for j in range(2,s):
            if(s%j ==0 ):
                flag = False
        if flag == True:
            answer+=1
    return answer

 

---

 

<참고한 개념>

 

1. 에라토스테네스의 체 : 2~n까지의 숫자들을 배수관계를 이용해 소수인지 아닌지를 찾아내는 알고리즘
2. combinatios() 함수 : 서로 다른 n개의 숫자 중 r개를 취하는 조합(순서상관없음, 내용조합중복없음) => nCr