프그스_완전탐색_소수 찾기_레벨2 (고득점 kit_소수_is_prime()_set)

• 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42839
• 여기에 제대로 된 is_prime()함수 구현함!!!

---

메모한 것

이거 permutations로 모든 경우의수 만들어놓고
하나씩 꺼내서 is_prime() 하면 되는거아님?

• (중요) 풀다가 놓쳐서 추가한 내용
  • is_prime()함수에서 0과 1은 제거해줘야함
  • 모든 경우의 수를 봐야하기 때문에 permutations를 쓰는건 맞음
    • 그래서 combinations를 쓰면 안되는데, 011같은 경우 1이 두개라 101같은게 두 번 나옴
    • 마지막에 set으로 중복제거를 해줘야함
    • 따라서 애초에 answer += 1이 아닌 answer.append()를 해주고 len()을 리턴해야됐음

---

솔루션 코드 - 내가 푼

## set 써야할거같음 -> combination은 쓰면 안됨 => 17과 71 둘다 나오기 때문

from itertools import permutations

def is_prime_number(x):
    # 소수는 1보다 큰 자연수 중 1과 자신을 약수로 갖는 수
    if x == 1 or x == 0:                    
        return False
    
    for i in range(2, x):      # 소수는 1보다 큰 자연수 중에서 이므로 2부터 계산
        if x % i == 0:         # 나머지가 0이된다 = 나눠지는 수가 있다면 소수 아님!
            return False
    return True

def solution(numbers):
    answer = []
    arr = list(map(int,numbers))
    leng = len(numbers)
    
    for j in range(1, leng+1):
        for i in permutations(arr, j):
            candidate = int("".join(map(str,i)))
            if is_prime_number(candidate):
                answer.append(candidate)
                
    return len(set(answer))

print(solution("17"))
print(solution("011"))

---

솔루션 코드 - 다른사람 풀이1

• 에라토스테네스 체 와 set을 사용한 풀이라고 함
• 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42839/solution_groups?language=python3

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

솔루션 코드 - 다른사람 풀이2

• 재귀를 사용한 풀이

primeSet = set()


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

    return True


def makeCombinations(str1, str2):
    if str1 != "":
        if isPrime(int(str1)):
            primeSet.add(int(str1))

    for i in range(len(str2)):
        makeCombinations(str1 + str2[i], str2[:i] + str2[i + 1:])


def solution(numbers):
    makeCombinations("", numbers)

    answer = len(primeSet)

    return answer