[프로그래머스] 소수 만들기(python) 복습

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/12977

사고 과정

• combinations로 만들 수 있는 수의 조합을 다 만들고 에라토스테네스의 체를 활용하여 소수를 찾았다.

나의 풀이

from itertools import combinations
def solution(nums):
    s = list(combinations(nums, 3))
    
    cnt = 0
    for i in s:
        for j in range(2, int(sum(i)**0.5)+1):
            if sum(i)%j == 0:
                break
        else:
            cnt+=1
    return cnt

에라토스테네스의 체

• 소수를 판별하는 알고리즘으로 대량의 소수를 빠르고 정확하게 구할 수 있다.
• 먼저 소수를 판별할 범위를 정하고, 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지워나간다.(2의 배수 지우고 3의 배수 지우고 ...) 이미 지워진 숫자는 건너뛴다. 그리고 마지막에 남아있는 숫자들이 소수이다.