[PROGRAMMERS]-소수 찾기 (완전탐색)

📃 소수 찾기

문제 풀이

소수 구하는 법

1. 2이상 n이하의 자연수 생성한다.

2. 그 자연수가 소수인지 아닌지 판별한다.

3. 소수라면 result에 1을 더한다.

4. 효율성을 위해 에라토스테네스의 체를 적용한다.

에라토라스의 체

• 이 방법으로 소수를 찾으려면 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다.

def solution(n):
    num = set(range(2, n+1))
    
    for i in range(2, n+1):
        if i in num:
            num -= set(range(2*i, n+1, i))
    return len(num)

|= 연산자

• |는 or 연산자이고 union을 뜻한다.
• |= 는 |의 결과를 update한다는 뜻
• |와 |=는 dictionary, counter, number 에 사용할 수 있다

 s1 = {"a", "b", "c"}
 s2 = {"d", "e", "f"}

  # OR, | 
  s1 | s2
  # >> {'a', 'b', 'c', 'd', 'e', 'f'}
  
  # `s1` is unchanged
     s1
  # >> {'a', 'b', 'c'}

  # In-place OR, |=
  s1 |= s2
  
  # `s1` is reassigned
  s1                                                    
  # >> {'a', 'b', 'c', 'd', 'e', 'f'}

코드

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)

나의 풀이

from itertools import permutations

def is_prime(num) : 
    if num < 2 :
        return False
    for i in range(2,(num//2)+1):
        if num % i == 0 : 
            return False 
    return True
        

def solution(numbers):
    answer = 0
    per = []
    # print(list(numbers)) -> ['1', '7']
    for i in range(len(numbers)):
        per+=list(map(''.join,permutations(list(numbers),i+1)))
        print(per)
    per = set(list(map(int,per)))

    for i in per : 
        if is_prime(i):
            answer += 1 
    return answer