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

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

문제가 다소 복잡해 보여서 어떤 순서로 해결해야될지 길게 고민한 끝에 아래와 같이 대략적인 코드 흐름을 짜고 코딩을 시작했다.
1️⃣ n을 k진수로 바꾸어서 string에 저장
2️⃣ 루프를 돌며 현재 숫자가 '0'이 아니면 string temp에 저장
3️⃣ '0'이라면 지금까지 저장했던 temp가 소수인지 판단

✅ 구현 코드

*전체 코드

#include <string>
#include <vector>
#include <cmath> // sqrt 사용하기 위한 헤더

using namespace std;

// 소수인지 판단하는 메서드
bool isPrime(const long long& tar)
{
    if (tar < 2) return false;
    if (tar == 2 || tar == 3) return true;
    if (tar % 2 == 0 || tar % 3 == 0) return false;

    for (int i = 5; i <= sqrt(tar); i += 6)
    {
        if (tar % i == 0 || tar % (i + 2) == 0) return false;
    }
    return true;
}

int solution(int n, int k)
{
    // 1. n을 k진수로 변환해 string에 저장
    string converted;
    while (n > 0)
    {
        converted = to_string(n % k) + converted;
        n /= k;
    }

    // 2.루프를 돌며 현재 ch가 '0'이 아니라면 temp에 저장, ch가 '0'이면 temp가 소수인지 판별
    string temp;
    int answer = 0;

    for (char ch : converted)
    {
        if (ch == '0')
        {
            if (!temp.empty() && isPrime(stoll(temp))) answer++;
            temp.clear();
        }
        else
        {
            temp.push_back(ch);
        }
    }

    // 3.마지막 temp에 저장된 숫자도 소수인지 판별
    if (!temp.empty() && isPrime(stoll(temp))) answer++;

    return answer;
}

🔹 bool isPrime(const long long& tar)

// 소수인지 판단하는 메서드
bool isPrime(const long long& tar)
{
    if (tar < 2) return false; // tar이 0과 1이라면 소수가 아니므로 false
    if (tar == 2 || tar == 3) return true; // tar이 2와 3이라면 소수 이므로 true
    if (tar % 2 == 0 || tar % 3 == 0) return false; // tar이 2와 3으로 나눠 떨어지면 false

    for (int i = 5; i <= sqrt(tar); i += 6)
    {
        if (tar % i == 0 || tar % (i + 2) == 0) return false;
    }
    return true;
}

앞에서 2와 3에 대한 검증이 끝났으므로, for문에서는 i를 5부터 6씩 증가하며, tar의 제곱근까지 탐색한다.
2와 3을 제외하고 다음 소수는 5, 7, 11, 13, 17, 19, 23, 29의 형태를 가지게 된다.
따라서 5부터 시작해서 6씩 증가하므로, i와 i + 2만 확인하면 tar이 아주 큰 수이더라도 빠르게 소수인지 판별할 수 있다.