[Python] 소수 찾기 - 완전 탐색

문제

해당 문제 링크

풀이

from itertools import permutations

def solution(numbers):
    answer = []
    num=[i for i in numbers]
  
    p=[]    
    for i in range(1,len(numbers)+1):
        p+=list(permutations(num, i))
    
    res=[int(('').join(j)) for j in p]
    
    res=set(res)
    res=list(res)
    print(res)
    
    for i in res:
        if i<2:
            continue
        check=True
        for j in range(2, i):
            if i%j==0: #소수 아님
                check=False
                break
        if check:
            answer.append(i)
    return len(answer)

Git - 소스 코드

결과

해석

코드 정리

    for i in numbers:
        num.append(i)

    num1=[i for i in numbers]

    res=[]
    for j in p:
        res+=[int(''.join(j))]
        
    res1=[int(''.join(j)) for j in p]

문제 접근이나 푸는 건 어렵지 않았지만, 쓰는 문법들을 잘 알아야 풀 수 있었다.
순열(permutations)를 사용하는 것과 .join을 쓰는 것이다.

res 배열에 값을 이어서 주고 싶다면 .join을 쓰게 되는데 이때 배열 변수에 넣는 것이기 때문에 밖에 []를 써야한다. 그렇지 않으면 배열에 값이 들어가지 않는다.

<소수 찾기 알고리즘>
[숫자 n 나누기]
1. 2부터 n-1까지 나누기

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

n-1까지, n이 1과 자기 자신 외의 수로 나누어지는지 판단하는 알고리즘이다. 만약 나누어진다면 바로 false를 리턴한다. n-1까지 걸리지 않는다면 True가 리턴된다. 가장 간단하고, 기초적이지만 오래 걸린다. 2부터 n-1까지의 수 모두를 확인하기 때문에, 시간 복잡도가 O(n)이다.

2. n/2까지 나누기

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

n의 모든 약수는 n/2보다 작다. 고로 2부터 n-1까지 확인할 필요가 없다는 뜻이다. 위 알고리즘보단 확인해야 할 조건이 반으로 줄었지만 여전히 시간 복잡도가 O(n)이기 때문에 느리다.

3. n의 제곱급까지 나누기

def isPrime(n):
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False  
    return True

n의 제곱근을 기준으로, 제곱근보다 작은 수들 중에 약수가 없다면, 제곱근보다 큰 수들은 n의 약수가 아니다. 예를 들어 n이 101이라면, √101+1까지의 수만 약수인지 확인해보면 된다. 만약 n/2 알고리즘을 쓰면 101//2+1 = 51, 즉 2~51까지 50번을 확인해야 하지만, n의 제곱근까지만 확인하면 √101+1 = 11, 즉 2~11까지 총 10번만 하면 된다. 그래서 시간 복잡도는 O(√n)으로, 1번의 방법들 중 제일 빠른 방법이다.

[에라토스테네스의 체]

def primeList(n):
    # n을 포함시키기 위함
    n += 1
    # [False(0), False(1), True(2), True(3), True(4) ... True(n)]
    sieve = [False, False] + [True] * (n)
    end = int(n**0.5) + 1
    for i in range(2, end):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False         
    return [i for i in range(n) if sieve[i] == True]

sieve라는 0~n까지의 숫자가 소수라면 True, 아니면 False 값을 담고 있는 배열을 생성한다. 그리고 최대 약수인 √n을 종료 값으로 설정한 뒤, 만약 sieve[i]값이 참이라면(=소수라면) 그 값의 배수들을 모두 거짓(=소수가 아님)으로 바꾼다. 그리고 마지막에는 sieve의 값에 따라, 참이라면 return 배열에 i를 추가하는 방식으로 사용할 수 있다.

def primeList(n):
    a = [False,False] + [True]*(n-1)
    primes=[]
    end = int(n**0.5) + 1
    for i in range(2, end):
        if a[i]:
            primes.append(i)
            for j in range(2*i, n, i):
                a[j] = False
    return primes

이런 식으로 사용해도 된다. list 대신 deque를 사용하면 시간 좀 더 단축된다.
설명 참고 사이트

그리고 문제를 풀면서 소수인 경우 배열에 값을 넣어줘야하는데 if else를 아래 코드와 같이 잘 못 사용하여서 오류를 많이 냈었다.
(처음 작성한 코드)

from itertools import permutations

def solution(numbers):
    answer = []
    num = []
    for i in numbers:
        num.append(i)
  
    p=[]    
    for i in range(1,len(numbers)+1):
        p+=list(permutations(num, i))
    
    res=[]
    for j in p:
        res+=[int(''.join(j))]
    
    res=set(res)
    res=list(res)
    # print(res)
    
    for i in res:
        if i<2:
            continue
        check=True
        for j in range(2, i):
            if i%j==0: #소수 아님
                check=False
                break
            else:
                answer.append(i)
                break
                    
    # print(answer)
    return len(answer)

이후 다른 사람의 코드를 참고하며 해석해서 잘못된 부분을 바로 잡을 수 있었다.