[Level 2] 소수 찾기

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

코딩테스트 연습 - 소수 찾기

▶ 에라토스테네스의 체 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

▶ 코드

# 에라토스테네스의 체 : N미만의 소수 찾아서 리스트로 반환 
def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    #print([i for i in range(2, n) if sieve[i] == True])
    return [i for i in range(2, n) if sieve[i] == True]

# numbers에 숫자 하나만 들어있을 경우, 그 숫자가 소수인지 판별 
def isPrime(n):
    c = 0
    for i in range(2, n+1):
        if n%i == 0:
            c += 1
    if c == 1:
        return True
    else:
        return False

def solution(numbers):
    if len(numbers) == 1:
        if isPrime(int(numbers)):
            #print(1)
            #print()
            return 1
        else:
            #print(0)
            #print()
            return 0
    
    t = []
    for a in numbers:
        t.append(int(a))
    t.sort(reverse=True)
    #print('t=', t)
    st = ''
    for a in t:
        st += str(a)
    st = int(st)
    #print('st =', st)
    lst = prime_list(st+1) # st+1 미만의 소수 찾아서 리스트로 반환  

    # 필터링 (각 소수 중, numbers에 없는 숫자 포함된것들을 필터링)
    temp = []
    for a in lst:
        flag = 0
        a = str(a)
        for b in a:
            if int(b) not in t:
                flag = 1
                break
        if flag == 0:
            temp.append(a)
    #print(temp)
    #print(len(temp))
    #print()

    # 필터링 (각 소수를 numbers와 자릿수마다 '해당 숫자' 개수 비교해 필터링)
    res = []
    for a in temp:
        flag = 0
        a = str(a)
        for b in a:
            if a.count(b) > t.count(int(b)):
                flag = 1
                break
        if flag == 0:
            res.append(a)
        
    #print(res)
    #print(len(res))
    #print()      
    
    return len(res)

#solution("013")
#solution("3")
#solution("4")
#solution("007")
#solution("070")
#solution("29")
#solution("17")
#solution("011")
#solution("1234")
#solution("7843")
#solution("999")