소수 찾기 (python, javascript)

프로그래머스 문제 소수 찾기 - LV2

https://programmers.co.kr/learn/courses/30/lessons/42839?language=python3
소수이용, 입력값의 범위가 작으므로 itertools.permutations(순열) 사용하여 모든 경우를 조사

👀 깃헙 소스

문제설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
numbers는 길이 1 이상 7 이하인 문자열입니다.

입출력 예

numbers	return
17	3
011	2

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

11과 011은 같은 숫자로 취급합니다.

솔루션
1부터 길이만큼의 순열을 구하고 join하여 붙여준 뒤 그 수가 소수인지 확인한다.

# 소수 구하는 코드 - 에라토스테네스의 체 
 N, primes = int('9' * L), set()
    
prime_check = [False, False] + [True]*(N-1) # 소수 체크
for i in range(2, N+1):
    if prime_check[i]:
        primes.add(i)
        prime_check[i*2::i] = [False] * len(prime_check[i*2::i])

코드

# 파이썬
from itertools import permutations
def solution(numbers):
    L = len(numbers)
    N, cand, primes = int('9' * L), set(), set()
    
    prime_check = [False, False] + [True]*(N-1) # 소수 체크
    for i in range(2, N+1):
        if prime_check[i]:
            primes.add(i)
            prime_check[i*2::i] = [False] * len(prime_check[i*2::i])
    
    for n in range(1, L+1):
        for x in permutations(numbers, n):
            number = int(''.join(x))
            if number in primes:
                cand.add(number)
            
    return len(cand)

// 자바스크립트
function solution(numbers) {
    const L = numbers.length;
    const MAX = 10**L - 1
    let primeSet = new Set()
    let cand = new Set()

    // 소수 체크
    let primes = [false, false]
    for (let i = 2; i <= MAX; i++) {
        primes.push(true)
    }
    for (let j = 2; j <= MAX; j++) {
        if (primes[j]) {
            primeSet.add(j)
            for (let k = 2 * j; k <= MAX; k += j) {
                primes[k] = false
            }
        }
    }

    // 순열
    function permutations(array, r) {                                                  
    // Algorythm copied from Python `itertools.permutations`.                      
    var n = array.length;                                                          
    if (r === undefined) {                                                         
        r = n;                                                                     
    }                                                                              
    if (r > n) {                                                                   
        return;                                                                    
    }                                                                              
    var indices = [];                                                              
    for (var i = 0; i < n; i++) {                                                  
        indices.push(i);                                                           
    }                                                                              
    var cycles = [];                                                               
    for (var i = n; i > n - r; i-- ) {                                             
        cycles.push(i);                                                            
    }                                                                              
    var results = [];                                                              
    var res = [];                                                                  
    for (var k = 0; k < r; k++) {                                                  
        res.push(array[indices[k]]);                                               
    }                                                                              
    results.push(res);                                                             
                                                                                   
    var broken = false;                                                            
    while (n > 0) {                                                                
        for (var i = r - 1; i >= 0; i--) {                                         
            cycles[i]--;                                                           
            if (cycles[i] === 0) {                                                 
                indices = indices.slice(0, i).concat(                              
                    indices.slice(i+1).concat(
                        indices.slice(i, i+1)));             
                cycles[i] = n - i;                                                 
                broken = false;                                                    
            } else {                                                               
                var j = cycles[i];                                                 
                var x = indices[i];                                                
                indices[i] = indices[n - j];                          
                indices[n - j] = x;                                   
                var res = [];
                for (var k = 0; k < r; k++) {                        
                    res.push(array[indices[k]]);                                   
                }                                                                  
                results.push(res);                                                 
                broken = true;                                                     
                break;                                                             
            }                                                                      
        }                                                                          
        if (broken === false) {                                                    
            break;                                                                 
        }                                                                          
    }                                                                              
    return results;                                                                
}     


    for (let k = 1; k <= numbers.length; k++) {
        for (let permu of permutations(numbers.split(''), k)){
            const item = Number(permu.join(''))
            if(primeSet.has(item)){
                cand.add(item)
            }
        }
    }
    return [...cand].length
}

팁
python에서 '001' 등을 int로 바꾸어줘도 1로 변환되어 예외처리 필요없음