[프로그래머스] 소수 찾기 _ 파이썬

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

프로그래머스

 

* 소수는 1과 자기 자신외에 나누어 떨어지지 않는 수를 말합니다.

 

 

1. 숫자 조각으로 만들 수 있는 모든 숫자 조합 찾기

python 의 itertools 모듈을 사용하면 간편하게 모든 조합을 찾을 수 있습니다. 여기서는 permutations 를 사용합니다.

from itertools import permutations

def get_all_combinations(numbers):
	all_combinations = set() # set 을 사용하여 중복된 숫자를 제거합니다.
    
    # 1자리부터 len(numbers) 자리까지의 모든 조합을 찾습니다.
    for i in range(1, len(numbers) + 1):
    	# permutations 를 사용해 i 자리의 모든 조합을 만듭니다.
        for combo in permutations(numbers, i ):
        # tuple을 문자열로 합쳐서 숫자로 변환합니다.
        number = int(''.join(combo))
        # set에 추가하여 중복을 제거합니다.
        all_combinations.add(number)
   return all_combinations

 

 

• permutations(numbers, i)는 numbers에서 i개의 숫자를 선택해 만들 수 있는 모든 순열을 생성합니다.
• ''.join(combo)는 tuple로 된 조합을 문자열로 합칩니다.
• int()는 문자열을 정수로 변환합니다.
• set을 사용하여 중복된 숫자를 제거합니다.

 

2. 소수 판별 함수 작성

 

주어진 숫자가 소수인지 판별하기 위해 다음의 방법을 사용합니다. 

def is_prime(n):
	if n < = 1:
    	return False # 1 이하의 숫자는 소수가 아닙니다.
	if n == 2:
    	return True # 2는 소수입니다.
	if n % 2 == 0 :
    	return False  # 짝수는 소수가 아닙니다.
	# 3부터 n의 제고급까지의 홀수로 나누어 떨어지는지 확인합니다.
    for i in range (3, int(n ** 0.5) + 1 , 2):
    	if n % i == 0:
        	return False # i 로 나누어 떨어지면 소수가 아님
	return True # 나누어 떨어지지 않으면 소수 입니다.
    

#테스트 예시
print(is_prime(29)) # True
print(is_prime(30)) # False

 

• 1 이하의 숫자는 소수가 아닙니다.
• 2는 유일한 짝수 소수입니다.
• 2로 나누어 떨어지는 수는 소수가 아닙니다.
• 3부터 n\sqrt{n}n​까지의 모든 홀수로 나누어 보아 나누어 떨어지면 소수가 아닙니다.

 

for 문 구조 설명

for i in range(3, int(n ** 0.5) + 1, 2): 구문은 3부터 n\sqrt{n}n​까지의 홀수만을 확인합니다. 이를 통해 효율적으로 소수 판별을 할 수 있습니다.

range 함수 이해
range(start, stop, step) 함수는 start에서 시작하여 stop 전까지 step 간격으로 숫자를 생성합니다.

 

 

for i in range(3, int(n ** 0.5) + 1, 2):

 

이 부분을 더 자세히 설명하면 다음과 같습니다:

1. start = 3: 3부터 시작합니다. 2는 이미 처리했기 때문에 홀수인 3부터 시작합니다.
2. stop = int(n ** 0.5) + 1: n\sqrt{n}n​의 정수 부분에 1을 더한 값까지 반복합니다.
   • 예를 들어, n이 25라면 25=5\sqrt{25} = 525​=5이므로, range(3, 6, 2)가 됩니다.
3. step = 2: 2씩 증가합니다. 즉, 홀수만 검사합니다.

 

3. 모든 조합에 대해 소수인지 판별

앞서 만든 조합과 소수 판별 함수를 사용해 최종적으로 소수의 개수를 셉니다.

def solution(numbers):
	all_combinations = get_all_combinations(numbers)
    prime_count = 0
    for number in all cobinations:
    	if is_prime(number):
        	prime_count += 1
	return prime_count

# 테스트 예시
print(solution("17")) # 3
print(solution("011")) # 2

 

• get_all_combinations(numbers)를 호출해 모든 가능한 숫자 조합을 구합니다.
• 각 조합 숫자가 소수인지 is_prime(number) 함수를 사용해 확인합니다.
• 소수인 경우 prime_count를 증가시킵니다

 

 

전체 코드

from itertools import permutations

def get_all_combinations(numbers):
    all_combinations = set()
    for i in range(1, len(numbers) + 1):
        for combo in permutations(numbers, i):
            number = int(''.join(combo))
            all_combinations.add(number)
    return all_combinations

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

def solution(numbers):
    all_combinations = get_all_combinations(numbers)
    prime_count = 0
    for number in all_combinations:
        if is_prime(number):
            prime_count += 1
    return prime_count

# 테스트 예시
print(solution("17"))  # 3
print(solution("011")) # 2