프로그래머스 소수 찾기 풀러 가기

문제 설명

구현 아이디어

1. 입력으로 주어진 값을 한 글자씩 자르자
2. 그 숫자들로 만들 수 있는 수들을 구하자
3. 그 수들 중 소수를 구하자

• 소수 - 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

소수 찾기 알고리즘 - 기본

2부터 그 수까지 반복문을 돌며 나눠떨어지는 수가 있는지 확인하면 된다.

만약 나눠떨어지는 수(= 약수)가 하나라도 있다면, 그 수는 소수가 아니다.

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

소수 찾기 알고리즘 - 조금 더 효율적으로

하지만, 2부터 number까지 for문을 다 도는 것은 좋은 방법이 아닌 것 같다 🤔
더 효율적인 방법을 찾아보자.

약수를 찾는 과정을 유심히 살펴보자.
사진에 표시한 연두색 줄을 기준으로는 수의 순서만 바뀌었을 뿐, 앞뒤로 짝을 이루는 것을 알 수 있다.

그러므로 나눠떨어지는지 확인하는 과정을 그 수의 제곱근까지만 진행하여도 된다.

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

• 제곱근이 실수가 나올 수 있으므로 int 변환을 해주고 1을 더해준다

전체 코드

import itertools
import math

# 소수 찾기
def isPrime(number):
    for i in range(2, int(math.sqrt(number))+1):
        if number % i == 0:
            return False
    return True

def solution(numbers): # numbers - "17", "011"
    # 1. 문자열을 한 글자씩 잘라서 숫자로 변환
    arr = list(map(int, list(numbers)))
    
    # 2. 순열을 구한다
    all = []
    for i in range(1, len(arr)+1):    
        all += list(itertools.permutations(arr, i))
    
    # 3. 리스트를 숫자로 변환
    # ex) [7, 1] → 71
    temp = []
    for elem in all:
        number = 0
        for i in range(len(elem)):
            number += 10 ** (len(elem)-1-i) * elem[i]
        temp.append(number)
    
    # 4. 중복되는 수 제거
    temp = list(set(temp))
    
    # 5. 소수로 구성된 리스트를 만듦
    answer = [num for num in temp if num > 1 and isPrime(num)]
    
    return len(answer)