프로그래머스 소수 찾기

시간 초과가 났는데, 잘 모르겠어서 다른 분의 코드를 참고했다. 에라토스테네스의 체를 효율적으로 작성해서 index 접근만으로 소수인지 아닌지 판단을 해야한다.

itertools 패키지의 permutations 모듈을 활용해 입력된 문자열화 된 숫자의 순열을 구한다.

'123'이라면 '1', '2', '3', '12', '23', '13', '123' 이런 식이다.

'011'이라면 '0', '1', '1', '01', '11', '011'인데 '1'과 '01'을 정수화하면 똑같은 1이고, '11', '011' 역시 정수화 하면 똑같이 11이다. 그래서 set()을 사용해서 중복을 제거해야 한다.

from itertools import permutations


def get_prime(n):
    primes = [False, False] + [True] * n  # [0, 1, 2, 3, ..., 9999999] 대신 T/F 사용
    for i in range(2, n):  # 소수는 2부터 시작이므로 2부터 9999999까지.
        if primes[i]:  # 인덱스 접근해서 True면 이 수의 배수를 False로 만듦
            j = i * 2  # 인덱스보다 2배 큰 수에 접근
            while n >= j:  # 인덱스가 9999999가 되지 않았으면 반복
                primes[j] = False  # 배수 False
                j += i  # 인덱스 배수에 접근
    return primes  # 인덱스가 소수인 것만 True


def get_combi(numbers, primes):
    result = set()  # 중복을 없애기 위함
    for i in range(1, len(numbers) + 1):  # 1자리부터 입력된 수의 길이만큼의 자리까지의 순열 만들기
        numberss = set(permutations(numbers, i))  # 중복없는 순열 생성
        for nums in numberss:  # 집합으로 싸인 튜플형태의 순열에 접근
            s = ''
            for num in nums:  # 튜플에 있는 값을 이어서 정수 만들기
                s += num
            n = int(s)
            if n < 2:  # 정수가 0, 1이면 다음 순열로 이동
                continue
            if primes[n]:  # 정수가 소수인지 판단
                result.add(n)  # 소수라면 집합에 추가
    return len(result)  # 집합에 있는 수를 세면 소수의 수가 나옴


def solution(numbers):
    primes = get_prime(10 ** 7)
    combi = get_combi(numbers, primes)
    return combi

 

출처

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

코딩테스트 연습 - 소수 찾기 | 프로그래머스

 

코딩테스트 연습 - 소수 찾기 | 프로그래머스

https://geonlee.tistory.com/115

[프로그래머스] 🕵️‍♀️ 소수 찾기 / python