k진수에서 소수 개수 구하기/C++

프로그래머스

 

풀이 방법

10진수인 n을 k진수 문자열로 변환하고 해당 문자열을 조건에 맞춰 파싱 후 소수의 개수를 리턴하면 된다.

 

 

 

1. n을 k진수 문자열로 변환하여 문자열 arithmetic에 담는다.

2. 문자열을 조건에 맞춰 파싱하여 tmp에 담고 숫자로 변환 후 소수인지 판별하고 소수면 answer++

3. 반복문이 끝난 후 tmp가 비어있지 않다면 한 번 더 소수인지 판별하고 소수면 answer++

4. answer 리턴

#include <string>
#include <vector>

using namespace std;

bool isPrime(long long n) {
    if(n < 2) return false;
    for(long long i=2; i*i<=n; i++)
        if(!(n % i)) return false;
    
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    string arithmetic = "";
    string tmp = "";
    
    while(n) {
        arithmetic += to_string(n % k);
        n /= k;
    }
    
    arithmetic = string(arithmetic.rbegin(), arithmetic.rend());
    
    for(int i = 0; i < arithmetic.length(); i++) {
        if(arithmetic[i] == '0' && !tmp.empty()) {
            long long num = stoll(tmp);
            if(isPrime(num)) answer++;
            tmp = "";
        }
        else tmp += arithmetic[i];
    }
    
    if(!tmp.empty()) {
        long long  n = stoll(tmp);
        if(isPrime(n)) answer++;
    }
    
    return answer;
}