k진수에서 소수 개수 구하기 92335

문제

접근 방법

0으로 끊어서 소수인지 확인해주는 문제라고 생각했다. k진수라는 것은 k로 나머지 연산 후 나눠주기를 반복하여 얻은 값들을 거꾸로 세워놓으면 해결된다.

코드

#include <string>
#include <cmath>
#include <stack>
using namespace std;
bool isPrime(long long num)
{
    if (num == 1)
        return false;
    for (long long i = 2; i <= sqrt(num); ++i)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}
int solution(int n, int k)
{
    stack<char> s;
    string number = "";
    int answer = 0;
    while (n)
    {
        char cur = n % k + '0';
        if (cur == '0')
        {
            while (!s.empty())
            {
                number += s.top();
                s.pop();
            }
            if (!number.empty())
            {
                if (isPrime(stoll(number)))
                    ++answer;
                number = "";
            }
        }
        else
            s.push(cur);
        n /= k;
    }
    while (!s.empty())
    {
        number += s.top();
        s.pop();
    }
    if (!number.empty() && isPrime(stoll(number)))
        ++answer;
    return answer;
}

풀이

소수 여러 개를 판단하는 것이기에 배열에 저장해두고 사용하는 방식으로 생각했다. 에라토스테네스의 채를 사용하여 저장해두고 푸는 방식을 말이다.
하지만 이 문제에서 나올 수 있는 값은 1,000,000자리의 수를 k진수로 만든 값이기에 배열의 범위를 넘는다.
그렇기에 숫자 하나에 대한 소수 판정을 해주는 방식으로 풀어주면 된다.