소수 찾기

첫 번째 풀이

def solution(numbers):
    from itertools import permutations  

    numbers = list(numbers)
    # print(numbers)
    combi = list(permutations(numbers, len(numbers)))
    strL = []

    for x in combi:
        X = ""
        for i in x:
            X += str(i)
        strL.append(int(X))
    
    L = list(set(strL))
    print(L)

    answer = 0
    for n in L:
        # 소수 판별 작업
        answer += 1

    return answer

가능한 모든 조합(순열)을 찾은 후에 소수 판별을 해주려고 했다. 하지만 문제를 제대로 안읽어서 입력이 "17" 일 경우 7도 된다는 걸 인지하지 못했다.

두 번째 풀이

def solution(numbers):
    from itertools import permutations  

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

    p = []
    result = []
    for i in range(1, len(numbers)+1): 
        p.extend(permutations(numbers, i))
    
    # print("p = ", p)
    # print()
    for a in p:
        # print("a = ", a)
        # print(''.join(a))
        # print(int(''.join(a)))
        result.append(int(''.join(a)))
    # print()

    # result =  [1, 7, 17, 71]
    answer = 0
    result = set(result)
    # print("result = ", result)

    for i in result:
        if checkFunc(i):
            answer+=1
    return answer

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

# numbers	= "17"	
# 3
# [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

numbers = "011"	
# 2
# [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.


print(solution(numbers))

정답 코드(주석 제거)

def solution(numbers):
    from itertools import permutations  

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

    p = []
    result = []
    for i in range(1, len(numbers)+1): 
        p.extend(permutations(numbers, i))

    for a in p:
        result.append(int(''.join(a)))

    answer = 0
    result = set(result)

    for i in result:
        if checkFunc(i):
            answer+=1
    return answer

extend()

array.extend(iterable) 형태로 사용한다. 입력한 iterable 자료형의 항목 각각을 array의 끝에 하나씩 추가한다. append와 동일하게 요소를 array의 끝에 추가하지만 append와 다른 점은 괄호( ) 안에는 iterable 자료형만 올 수 있다는 것이다. iterable 자료형이 아닌 경우 TypeError가 발생한다. 사용 예시는 아래와 같다.

nums = [1, 2, 3]
nums.extend([4, 5])
[1, 2, 3, 4, 5]  #리스트로 주어진 [4, 5]의 요소가 각각 추가 되었음

a = [10]
nums.extend(a) 
[1, 2, 3, 4, 5, 10]

괄호 안에 iterable 자료형만 입력할 수 있기 때문에 요소 하나를 추가하려면 리스트와 같은 iterable 자료형으로 변환하여 입력해야 한다. 그런데 요소 하나만 추가한다면 굳이 extend 함수를 사용하기보다는 append 함수를 사용하는 것이 편리하겠다. 반면 append 함수는 iterable 자료형의 요소를 각각 추가하는 것이 불가능하니 그럴 때는 extend 함수를 사용할 수 있겠다.

소수 판별 알고리즘

import math

# 소수 판별
def primenumber(x):
    for i in range (2, int(math.sqrt(x) + 1):	# 2부터 x의 제곱근까지의 숫자
    	if x % i == 0:		# 나눠떨어지는 숫자가 있으면 소수가 아님
        	return False
    return True				# 전부 나눠떨어지지 않는다면 소수임

에라토스테네스의 체

import math

n = 1000	# 2부터 1000까지 모든 수에 대하여 소수를 찾을 것이다.
array = [True for i in range(n + 1) # 0,1을 제외한 모든 숫자가 소수(True)인 것으로 설정하고 시작한다.

# 에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인
	if array[i] == True:	# i가 소수인 경우
    	# i를 제외한 i의 모든 배수를 지우기
        j = 2
        while i * j <= n:
        	array[i * j] = False
            j += 1
            
#모든 소수 출력
for i range(2, n + 1):
	if array[i]:
    	print(i, end = ' ')