k진수에서 소수 개수 구하기 (풀이)

 

프로그래머스

from math import sqrt as sq

def prime(x):
    if x <= 1:
        return False

    for i in range(3, int(sq(x) + 1), 2):
    # for i in range(2, int(sq(x) + 1)):
		# 3의 배수부터 +2 단위씩 리스트 출력 = len 49
		# 확실히 2의부터 만드는 것보다 훨씬 시간 절약 = len 99
        if x % i == 0:
				# 각 소수의 배수는 삭제
            return False
		# 그 이외의 것들만 출력
    return True

def solution(n, k):
    answer = 0
    trans = ''
    while n > 0:
        re= n % k # 변수로 만들어 주는게 시간 절약(사견)
				# 나머지 값 저장
        trans = str(re) + trans
        n //= k # n = n // k 와 동일

    nums = [int(n) for n in trans .split('0') if n != '']
		# 아래 코드와 동일 / 한줄 for문이 시간 절약
		#nums = [] 
    # for num in number.split('0'):
    #     if num:
    #         nums.append(int(num))

    con = 0
    for n in nums:
        if prime(n): # 소수면 + 1
            con += 1
    return con

# 45.44

위에 있는 코드가 내가 처음에 완성한 코드다.

n기수 분의 코드를 추가해 소수판별 함수(prime)의 조건과 소수 리스트의 갯수를 줄여주었다.

# 최종 코드 (n기수분 코드 참고)
from math import sqrt as sq
def prime(x):
    if x <= 1:
        return False
    if x in (2, 3):
        return True
    if x % 2 == 0 or x % 3 == 0:
        return False
    if x < 9:
        return True
    for i in range(5, int(sq(x) + 1), 6):    
        if x % i == 0 or x % i + 2 == 0:
            return False
    return True

def solution(n, k):
    answer = 0
    number = ''
    while n > 0:
        remain = n % k
        number = str(remain) + number
        n //= k

    nums = [int(n) for n in number.split('0') if n != '']
    con = 0
    for n in nums:
        if prime(n):
            con += 1
    return con

# 35.11

3의 배수 2의 증가였던 리스트가 5의 배수 6증가로 변경해주고, 애초에 입력 값 x < 9 이하면 바로 값을 True로 넘겨주면 된다.

속도가 무려 11초가 줄어들었다.

확실히 읽어야 하는 리스트의 값이 줄어듦에 따라 시간 절약되는 모습을 볼 수 있다.