[프로그래머스] Lv2 소수 찾기 - python

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

풀이

모든 경우의 수를 permutations를 사용하여 순열로 뽑아내었다. list로 나온 요소를 모두 join 메서드를 사용하여 이어붙인 뒤 숫자로 변환하였다. 문제에서 011과 11은 같은 숫자라고 명시했기 때문에 중복을 제거한 뒤 모든 경우를 소수 판별했다. 0과 1은 소수가 아니므로 예외처리를 해주고 그 외의 경우에는 1, 자기자신을 제외한 수로 모두 나눠보며 체크했다.

 

프로그래머스 내에서는 통과되었는데 분명 시간초과가 날 여지가 있다고 생각하여 소수판별 알고리즘을 한번 더 정리해보려 한다. 블로그에 이미 올려둔 내용이긴 하지만... 또 까먹었기 때문에 한번 더 정리

 

# 2022-07-22
# 프로그래머스 Lv2 - 소수 찾기
# https://school.programmers.co.kr/learn/courses/30/lessons/42839
# 소요시간 : 15:10 ~ 15:25 (15m)

from itertools import permutations

# 소수판별 알고리즘
def checkPrimeNum(num):
    if num == 0 or num == 1:
        return False

    for i in range(2, num):
        if num % i == 0:
            return False
    return True


def solution(numbers):
    answer = 0
    num_arr = []
    for num in numbers:
        num_arr.append(num)

    every_case = []
    for i in range(1, len(num_arr) + 1):
        case = list(permutations(num_arr, i))
        for arr in case:
            every_case.append(int("".join(arr)))

    every_case = list(set(every_case))

    for case in every_case:
        if checkPrimeNum(case):
            answer += 1

    return answer

 

소수 판별 알고리즘

단일 숫자 판별 시

약수의 성질을 살펴보면 모든 약수는 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다. 

16의 약수는 1, 2, 4, 8, 16 인데 2x8 = 16, 8x2=16이다.

따라서 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인해주면 된다. 

 

# 소수 판별 (개선된 알고리즘)
import math

def isPrimeNumber(num):
    # 2부터 num의 제곱근까지의 모든 수를 확인하기
    # 제곱근을 구하는 방법은 math.sqrt() 사용. 반환형은 float
    # 음수의 제곱근을 구하게 되면 error 발생하니 유의
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

 

대량의 숫자 판별 시 (에라토스테네스의 체)

이 문제에서는 각각의 경우가 소수인지 판단해야 되서 아니지만, 만약 특정 범위까지의 자연수 중 소수가 몇개인지처럼 대량의 소수를 한꺼번에 판별하고자 할 때 사용하면 좋은 방법을 추가로 정리한다.

 

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당, 그 인덱스에 해당하는 값을 넣어준다. 2부터 시작하여 특정 숫자의 배수에 해당하는 숫자를 모두 지운다. (자기 자신은 지우지 않음) 

 

n = int(input())

eratos = [True] * (n+1)
m = int(n**0.5) // math.sqrt 사용해도 ok

for i in range(2, m+1):
	if eratos[i] == True:
    	for j in range(i+i, n+1, i): #i의 배수를 모두 삭제, 본인은 제외
        	eratos[j] = False
            
print([i for i in range(2, n+1) if a[i] == True])