소수 판별하기: 기본, 제곱근, 에라토스테네스의 체 / Python / 예제 - Programmers 소수찾기

Prime Number, 소수

1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수

 

 

소수 판별하기

1. 기본 알고리즘: 완전탐색
   • 2부터 x-1 까지 모든 수에 대하여 나누어 떨어지는지 확인
   • 모든 수를 확인해야하므로 시간복잡도는 O(X)

     def is_prime_number1(x: int):
     for i in range(2, x): # 2부터 x-1 까지의 모든 수를 확인
       if x % i == 0: # x가 해당 수로 나누어 떨어진다면
           return False # 소수가 아님
     return True # 소수임

2. 제곱근을 이용하기  
   • 약수는 배수의 특징을 가지고 있다. 
   • 가운데 약수(제곱근)을 기준으로 곱셈 연산에 대해 대칭을 이룬다. 따라서, 특정 자연수 x가 소수인지 판별하기 위해서는 제곱근까지만 확인하면 된다.
     • 2 * 8과 8 * 2는 대칭이다. 2로 나누어 떨어진다면, 8로도 나누어 떨어진다. 
     • 8은 2의 배수이다.

# 소수 판별: 제곱근 이용
def is_prime_number2(x):
    # for i in range(2, int(math.sqrt(x)) + 1): # math 라이브러리 이용
    # x ** 0.5: 제곱근 구하는 식
    for i in range(2, int(x ** 0.5) + 1):
        if i % 1 == 0:
            return False
    return True

 

 

에라토스테네스의 체

동작 과정

• 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘
• N보다 작거나 같은 모든 소수를 찾을 때 사용
• 위에서 사용한 약수의 성질을 이용하여 제곱근까지만 확인해도 된다.
• 동작과정
  • 2부터 N가지의 모든 자연수를 나열
  • 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
  • 남은 수 중에서 i의 배수를 모두 제거(i는 제거하지 않는다.)
  • 더이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복

def sieve_of_eratosthenes(x):
    arr = [True for _ in range(x + 1)] # x 까지의 수
    for i in range(2, int(x ** 0.5) + 1): # 2부터 자연수 x의 제곱근까지 확인
        if arr[i] == True: # i가 소수인 경우
            j = 2
            while i * j <= x: # i를 제외한 i의 모든 배수를 지우기
                arr[i * j] = False
                j += 1

    return [i for i in range(2, x + 1) if arr[i]] # 모든 소수를 리턴

 

 

예제

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

프로그래머스

종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return

 

문제풀이

1. 완전탐색이므로, 가능한 모든 숫자의 조합 찾기
2. 해당 수가 소수라면 정답에 추가하기

from itertools import permutations

def solution(numbers):
    answers = set()
    for size in range(1, len(numbers) + 1):
        n_combi = list(permutations(numbers, size)) # 가능한 모든 소수 구하기

        for combi in n_combi:
            now = int("".join(combi)) 
            if now > 1 and is_prime(now): # 해당 수가 소수라면
                answers.add(now) # 정답에 추가

    return len(answers) # 만들 수 있는 소수의 개수 반환

# 소수인지 판별
def is_prime(x):
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True