python 코딩테스트 대비하기2 소수찾기

소수 찾기 함수 (암기 필요!!)

- 실행시간 단축을 위해 제곱근+1까지만 for문 반복

- 1은 무조건 False

- for문은 2부터 n**(1/2)+1까지인데 이때 int()를 n제곱근 앞에 씌워줘야하는 것 잊지말기

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

출처: https://www.youtube.com/watch?v=LD-Px5YCd8Y 

이 함수를 이용해서 풀 수 있는 문제

K진수에서 소수 개수 구하기

https://school.programmers.co.kr/learn/courses/30/lessons/92335?itm_content=course14743 

프로그래머스

필요한 것

- 소수 개수 구하는 함수

- 10진수를 k진수로 변환하는 함수

(참고: https://velog.io/@code_angler/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%A7%84%EC%88%98%EB%B3%80%ED%99%982%EC%A7%84%EB%B2%95-3%EC%A7%84%EB%B2%95-5%EC%A7%84%EB%B2%95-10%EC%A7%84%EB%B2%95n%EC%A7%84%EB%B2%95)

https://www.youtube.com/watch?v=wtcRGMwU83A

(10진수 이하일때 유효)

2진법 bin

8진법 oct()

16진법 hex()

 

제출한 코드

def solution(n, k):

    # 암기함
    def isprime(i):
        if i == 1: return False
        for j in range(2, int(i**(1/2))+1):
            if i % j == 0: return False
        return True
        
    # 블로그 참고
    def solution(n, q):
        rev_base = ''
        while n > 0:
            n, mod = divmod(n, q)
            rev_base += str(mod)
        return rev_base[::-1] 
    
    new_n = solution(n, k)
    list1 = new_n.split('0')
    list2 = [v for v in list1 if v] # 리스트 안에 '' 제거하기
    list3 = list(map(int, list2))
    print(list3)
    return sum(list(map(isprime, list3)))

코드 아래 부분이 좀 더러운데,,,, 다른 사람의 풀이를 참고해보자.

 

# 다른 사람의 풀이
# n을 k진법으로 나타낸 문자열 반환
def conv(n, k):
    s = ''
    while n:
        s += str(n%k)
        n //= k
    return s[::-1]

# n이 소수인지 판정
def isprime(n):
    if n <= 1: return False
    i = 2
    while i*i <= n:
        if n%i == 0: return False
        i += 1
    return True

def solution(n, k):
    s = conv(n,k)
    cnt = 0
    for num in s.split('0'):
        if not num: continue # 빈 문자열에 대한 예외처리
        if isprime(int(num)): cnt += 1
    return cnt