[코딩테스트 python] k진수에서 소수 개수 구하기

 

프로그래머스

 

 

주의사항
: 해당 k진수로 변환했을 때 0으로 나눈 수 기준
> 그 수를 k진법이 아닌 10진수로 봤을 때 소수 여부

(문제를 꼼꼼히 읽자...!!!!😭)

 

def k_num(n, k):  #k진법으로 변환
    if k == 10:
        return n  #10진수면 그대로 반환
    else:
        base = ''
        while n > 0:
            n, mod = divmod(n, k)
            base += str(mod)
        return base[::-1]

def prime_num(num): #소수여부 판단
    p_cnt = 0
    for k in range(1,int(num**(1/2)+1)):
        if num % k == 0:
            p_cnt +=1
            if p_cnt >= 2:
                break
    if p_cnt == 1:
        return True
    else:
        return False

def solution(n, k): #실행함수
    answer = 0
    list_k = str(k_num(n, k)).split('0') #문자열로 변환하여 '0'을 기준으로 숫자 분리
    for l in list_k:
        stop = ['', '1']
        if l not in stop and prime_num(int(l)):
            answer+=1
    return answer

처음 소수 여부 판단하는 함수에서 
range(1, num)으로 했다가 "시간 초과"
>> 1번 테스트 케이스에서 "시간 초과" OR "실패"의 힌트를 보고 
아차 싶어서 제곱근의 절반으로 범위 수정

그 다음은 1도 소수라고 생각해서 넣었는데
소수 정의 = 1과 자기자신.
즉, 1은 소수가 아님! 제외가 맞음

 

다른 분 풀이 확인 했을 때 
소수 여부 판단은 더 간결하게 가능👍

def prime_num(num): #소수여부 판단
	#while문 사용
    i = 2
    while i*i <=n:
    	if n%i == 0:
        	return False
           i += 1
    return True
    
    #for문 사용
    for k in range(2,int(num**(1/2)+1)):
        if num % k == 0:
            return False
    return True

굳이 count==1을 하지 않고
return을 사용해서
중간에 나누어 떨어지면 False,
for문을 완수하면 나누어떨어진 것이 없다는 뜻이니까 True.

>> 불필요한 p_cnt를 추가하니 시간이 훨씬 더 걸림

 

* 참고: 진법 변환 정리

[python] 진법&자료형 변환 Casting 함수