IT-garden

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한조건

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

입출력 예 설명

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

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

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

나의 풀이

from itertools import permutations

def solution(numbers):
    r=[]
    for i in range(1,len(numbers)+1):
        for j in permutations(list(numbers),i):
            jj=int(''.join(j))
            for k in range(2,jj):
                if jj % k == 0:
                    break
            else:
                if jj not in r and jj != 0 and jj != 1:
                    r.append(jj)
    return len(r)

1. 문자열 numbers를 한자리의 수부터 len(numbers)의 수까지 순열로 만듭니다.
2. 각각의 수가 소수인지 검사하여 소수이면 리스트 r에 넣습니다.
3. 리스트 r에 있는 소수의 개수를 리턴합니다.

프로그래머스 '소수 찾기' : https://programmers.co.kr/learn/courses/30/lessons/42839

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한조건

• n은 2이상 1000000이하의 자연수입니다.
  
  

입출력 예

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

나의 풀이

def solution(n):
    n = n + 1
    answer= [True] * n
    for i in range(2,int(n**0.5)+1):
        if answer[i] == True:
            for j in range(i+i,n,i):
                answer[j]=False
    a=[i for i in range(2,n) if answer[i]== True]

    return len(a)

1. 리스트 answer을 모두 소수라고 생각해 True로 값을 설정합니다.
2. 2부터 int(n**0.5)까지 소수인지 확인합니다.
   int(n**0.5)인 이유는 n의 최대 약수가 int(n**0.5)이하이기 때문입니다.
3. 2번에서 소수인 숫자의 배수들은 소수가 아니기 때문에 다음 for문에서 소수가 아니라고 False로 설정해줍니다.
4. 2번과 3번의 과정을 반복합니다.
5. 리스트 answer의 값이 True인(소수인 것) 값들의 개수를 리턴합니다.

다른 사람의 풀이

def solution(n):
    num=set(range(2,n+1))
    print('num',num)

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

2부터 n까지 중복제거한 리스트를 생성합니다.
2부터 n까지 소수인지 확인하는 과정에서 소수인 숫자의 배수들은 set을 통해 제거하여 num을 설정해줍니다.
이 과정을 반복하고 num의 길이를 리턴합니다.

프로그래머스 '소수 찾기' : https://programmers.co.kr/learn/courses/30/lessons/12921