프로그래머스 | 소수 만들기 (파이썬) combination, 에라토스테네스의 체

 

오늘도 오랑이는 문제를 풉니다. 

 

소수 만들기

 

 

풀이 과정

해당 문제는 크게 두 파트로 나눠서 풀어야 합니다.

• nums 의 값 3개씩 조합
• 소수 판별

첫번째 조건에 대한 코드를 짜봅니다.

def solution(nums):
    for i in range(len(nums)):
        for j in range(i+1,len(nums)):
            for k in range(j+1,len(nums)):
                num = nums[i] + nums[j] + nums[k]

 

예전에 풀었던 삼총사 문제와 동일한 방식입니다.

 

어떤 수 n이 소수가 되려면 인수가 1과 자기 자신 n 뿐이어야 합니다. 

또한 0 과 1 은 소수가 될 수 없습니다. 

즉, n 은 2 이상의 숫자가 되며 그 인수 또한 2 이상이어야 합니다. 

 

다른 말로 n보다 작은 수 i에 대해서, n을 i로 나눴을 때 나머지가 0인 경우가 없어야 한다는 뜻이지요.

 

n 대신 앞에서 구한 숫자들의 합 num 을 넣어서 코드로 짜보면 아래와 같습니다.

chk = True 를 미리 선언해주고 1과 자기자신 외의 인수가 있을 경우 False로 바꿔주는 작업을 해주고,

그게 아닌 경우 그대로 True 를 리턴하며 횟수를 세어줍니다. 

chk = True
for n in range(2,num):
    if num%n==0:
        chk = False
if chk == True:
    answer += 1

 

소수를 구하는 가장 정석적인 방법이라고 할 수 있습니다.

다만 num이 클 경우, 시간이 오래 걸릴 수 있으니 num의 제곱근까지만 확인해서 시간을 줄여줍니다.

소수가 아닌 수의 경우, 모든 인수는 해당 수의 제곱근보다 작은 인수와 제곱근보다 큰 인수가 하나씩 짝지어지거나 제곱근 자체가 인수가 됩니다니다. 

하지만 소수의 경우, 여기에 해당되는 수가 없을 거기 때문에 제곱근까지만 확인해주면 된다는 사실.

이때는 범위를 제곱근까지 포함하도록 +1을 해줍니다. 

 

최종 코드

def solution(nums):
    answer = 0
    for i in range(len(nums)):
        for j in range(i+1,len(nums)):
            for k in range(j+1,len(nums)):
                num = nums[i] + nums[j] + nums[k]
                chk = True
                for n in range(2,int(num**0.5)+1):
                    if num%n==0:
                        chk = False
                        break
                if chk == True:
                    answer += 1
    return answer

 

해당 풀이에서는 for 문을 세 번 이용하면서 각각 i, j, k 에 대한 범위를 설정했는데, 이보다 간단하게 combination 라이브러리를 사용해서 한 번에 기술할 수도 있습니다. 

 

from itertools import combinations

for i in combinations(nums, 3):
    num = sum(i)
    
# 아래와 동일한 결과 출력 

for i in range(len(nums)):
    for j in range(i+1,len(nums)):
        for k in range(j+1,len(nums)):
            num = nums[i] + nums[j] + nums[k]

 

 

사실 위의 방법으로도 숫자가 너무 커질 경우 시간 문제가 생길 수 있다고 합니다. 

이때 활용할 수 있는 것이 에라토스테네스의 체라는 알고리즘 기법인데요. 

 

에라토스테네스의 체

 

n 까지의 범위 내에서 순차적으로 돌면서 합성수를 제거하는 방식으로 작동합니다.

• 1 제거
• 2 소수로 지정, 2의 배수 모두 제거
• 3 소수로 지정, 3의 배수 모두 제거
• 4 이미 제거됨
• 5 소수로 지정, 5의 배수 모두 제거 
• ...

 

n까지의 모든 소수를 돌려주는 코드는 아래와 같습니다. 

n=1000

def isPrime(n):
a = [False,False] + [True]*(n-1)   # 0, 1 은 소수가 될 수 없기 때문에 False로 선언
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):   #해당 수의 모든 배수는 False 로 지정
        a[j] = False
return primes

 

 

 

 

오랑우탄이 영어를 하고 오랑이가 코드마스터가 되는 그날까지~

 

 

 

프로그래머스