38. 소수 만들기 (소수 판별 알고리즘)

유형 : 구현

풀이 시간 : 20분

 

def solution(nums):
    answer = -1
    from itertools import combinations
    sumnum = []
    for number in combinations(nums, 3):
        cnt = sum(number)
        sumnum.append(cnt)
    sumnum.sort(reverse = True)
    answer = 0
    for i in range(len(sumnum)):
        if check(sumnum[i]) == False:
            answer += 1
    return answer

def check(num):
    import math
    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0 and i != num:
            return True
    return False

 

소수 판별을 하기 위한 기본적인 알고리즘을 사용했다. 

itertools - combianation도 사용. 

 

def check(num):
    import math
    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0 and i != num:
            return True
    return False

 

=> 소수 판별을 위해 num의 제곱근까지만 확인한다.