[Algorithm🧬] 소수 만들기

문제 / 풀이.py, 풀이.swift

python

import math

def isPrime(num):
    for i in range(2, int(math.pow(num, 0.5))+1):
        if num % i == 0:
            return False
    else:

        return True

def solution(nums):
    answer = 0
    sum = 0
    
    # 배열에서 3개 뽑아서
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            for k in range(j+1, len(nums)):
                # 더한 후
                sum = nums[i] + nums[j] + nums[k]
                # 소수이면 count
                if isPrime(sum):
                    answer += 1

    return answer

for문을 돌려서 3개를 뽑기가 싫어서... 다른 방법을 강구해봤지만 내 지식으로는 이게 최선인 것 같았다.

다른 사람들의 답변

def solution(nums):
    from itertools import combinations as cb
    # itertools 의 combinations 를 이용하면 3개를 뽑아준다는 사실을 알게 되었다.. 그러네 이름부터 조합이네
    answer = 0
    for a in cb(nums, 3):
        cand = sum(a)
        for j in range(2, cand):
            if cand%j==0:
                break
        else:
            answer += 1
    return answ

isPrime 도 루트까지 도는거 말고

(5, 2) = (2, 5%2) = (2, 1) = (1, 2%1) = (1, 0) = 1 이렇게 푸는거... 무슨 방법이더라.. 근데 결국 이것도 재귀를 써야할 것 같아서 반복문에 break를 거는게 빠를 것 같았다.

210121 swift

역시나.. swift 에는 오픈소스 말고는 아직 조합을 구현해둔 소스가 없는 것 같다. 파이썬 공부도 놓지 말아야겠다.

python itertools
swift 조합, 순열 직접 구현

두가지를 추가로 공부해보자!!

import Foundation
func isPrime(num: Int) -> Bool {
    if num < 2 {
        return false
    }
    
    let root = Int(pow(Double(num), 0.5))
    for i in 2..<root+1 {
        if num % i == 0 {
            return false
        }
    }
    return true
}

func solution(_ nums:[Int]) -> Int {
    var answer = 0

    for i in nums.indices {
        for j in i+1..<nums.count {
            for k in j+1..<nums.count {
                if isPrime(num: nums[i] + nums[j] + nums[k]) {
                    answer += 1
                }
            }
        }
    }
    
    return answer
}