C++:: 프로그래머스 < k진수에서 소수 개수 구하기 >

처음에 소수를 판별하는 부분을 에라토스테네스의 체로 구현하였는데 판별해야하는 수가 long long 범위의 수일 수도 있기때문에 각 수에대해 판별을 따로 해주어야한다. 이를 주의한다면 크게 어렵지는 않은 문제이다.

#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

bool is_prime(long long n)
{// 소수 판별
    if (n == 1) return false;
    int num = sqrt(n);
    for(int i=2;i<=num;i++)
        if (n%i == 0) return false;
    return true;
}

int solution(int n, int k)
{
    int answer = 0;
    vector<long long> res, tmp;
    while (n > 0)
    {//tmp에 k진수로 변환한 하나하나의 숫자를 넣어준다.
        tmp.push_back(n % k);
        n = (n - n % k)/k;
    }
    reverse(tmp.begin(), tmp.end());// 애초에 거꾸로 들어가기때문에 되돌려서 원래대로 바꿔준다.
    long long num = 0;
    for(auto c : tmp)
    {// 0이 아닌 수들은 붙여준다고 생각하면 된다.
        if (c) num = num*10 + c;
        else if (num)
        {
            res.push_back(num);
            num = 0;
        }
    }
    if (num) res.push_back(num);
    for(auto c : res) if (is_prime(c)) answer++;
    return answer;
}