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

Gyuhan Park·2021년 7월 23일
0

코딩테스트 정복

목록 보기
15/47

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

주어진 숫자 중 서로 다른 3개를 더해 소수가 되는 경우의 수를 구하라.

서로 다른 3개가 될 수 있는 모든 경우의 수를 구한다. 각각의 경우의 수의 숫자 3개를 더한 값을 가지고 소수를 판별한다. 소수 판별에는 여러가지 방법이 있지만 제곱근의 약수까지만 찾는 방법을 택해 문제를 풀었다.

# 정답코드

import math
from itertools import combinations  

def solution(nums):
    answer = 0
    numbers = list(combinations(nums, 3))
    for i in numbers:
        target = sum(i)
        for j in range(2, int(math.sqrt(target)) + 1):
            if target % j == 0:
                break
            elif j == int(math.sqrt(target)):
                answer += 1        
            
    return answer    
        

# 소수판별법

소수(Prime number) : 1과 자기 자신만을 약수로 갖는 수

  1. 2부터 (n-1)까지의 모든 수를 확인하여 x가 나누어떨어지는 수가 있다면 x는 소수가 아니다.
    모든 수를 확인하므로 시간 복잡도 : O(N)
  2. 모든 약수는 가운데 약수(제곱근)을 기준으로 곱셈 연산에 대해 대칭인 성질을 사용한다.
    ex) 16의 약수 : 1, 2, 4, 8, 16 / 1 x 16 == 2 x 8, 따라서 4까지만 확인하면 모든 약수를 확인하는 것과 같다.
    2부터 x의 제곱근까지의 모든 수를 확인하며 x가 해당 수로 나누어떨어진다면 소수가 아니다. 시간복잡도 : O(N^1/2)
import math

def is_prime_number(x):
    for i in range(2, int(math.sqrt(x))+1):
    if x % i == 0:
        return False
    return True

3. 에라토스테네스의 체(가장 빠름!!)

찾는 수까지 True로 채운 리스트를 만든다. 2를 제외한 2의 배수, 3을 제외한 3의 배수와 같이 sqrt(n)의 배수는 모두 False로 만든다. 2~n까지의 숫자들 중 True인 숫자들이 소수다.
이는 범위에 대한 소수 판별에 유리하다. 시간복잡도 : O(Nlog(logN))

def is_prime_number(n):
    # 2부터 n까지의 모든 수에 대하여 소수 판별
    array = [True for i in range(n+1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)

    # 에라토스테네스의 체
    for i in range(2, int(math.sqrt(n)) + 1): #2부터 n의 제곱근까지의 모든 수를 확인하며
        if array[i] == True: # i가 소수인 경우 i를 제외한 i의 모든 배수를 지우기
            j = 2
            while i * j <= n:
                array[i * j] = False
                j += 1

    return [ i for i in range(2, n+1) if array[i] ]
profile
단단한 프론트엔드 개발자가 되고 싶은

0개의 댓글