[프로그래머스] k진수에서 소수 개수 구하기

---

🔗 문제 링크

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

프로그래머스

---

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool isPrime(long number) {
    if (number <= 1) {
        return false;
    }
    
    if (number <= 3) {
        return true;
    }

    if (number % 2 == 0 || number % 3 == 0) {
        return false; 
    }
        
    for (long i = 5; i * i <= number; i += 6) {
        if (number % i == 0 || number % (i + 2) == 0) {
            return false;
        }
    }

    return true;
}

int solution(int n, int k) {
    int answer = 0;
    string number = "";
    string temp = "";
    
    while(n > 0){
        number += to_string(n % k);
        n /= k;
    }
    
    reverse(number.begin(), number.end());
    
    for(auto n : number){
        if(n == '0'){
            if(isPrime(stol(temp))){
                answer++;
            }
            
           temp = "";
        }
        
        temp += n;
    }
    
    if (!temp.empty()) {
        if (isPrime(stol(temp))) {
            answer++;
        }
    }
    
    return answer;
}

---

📝 풀이

우선 주어진 수 n을 k진수에 맞춰 변환합니다.

⭐참고⭐ 2024.08.12 - [코딩테스트/프로그래머스] - [프로그래머스] [3차] n진수 게임

 

반복문을 돌며 변환된 숫자 number 중 '0'이 나오는 경우 숫자가 소수인지 확인합니다.

소수를 확인하는 기준은 '0'으로 구분되기 때문에 temp에 저장해두었다가 '0'이 나오면 초기화합니다.

 

숫자가 소수인지를 판별하는 함수(isPrime)는 따로 구현하였습니다.

0~3까지는 예외처리를 하고 우선적으로 2와 3으로 나누어 소수를 판별합니다.

그 외의 숫자는 5부터 숫자의 제곱근까지 확인합니다.

6의 배수와 2를 더한 숫자로 나누어 떨어지면 소수가 아닙니다.

 

반복문이 끝난 후 소수 양쪽에 아무것도 없는 경우가 존재 할 수 있으니 한 번 더 소수 판별을 합니다.

최종적으로 카운팅된 answer를 return 합니다.