[c++ programmers 2022 kakao blind recruitment - k진수에서 소수 개수 구하기]

#include <string>
#include <vector>
#include <iostream>
#include <math.h>
using namespace std;

string temp = "";

vector<long long> numbers;


void conv(int number, int n){
    while (number > 0){
        if (number % n < 10){
            temp += number % n + 48;
        }
        else{
            temp += number % n + 55;
        }
        number /= n;
    } 
}

int solution(int n, int k) {
    int answer = 0;
    
    conv(n, k);
    
    long long c = temp.size() - 1;

    int f = 0;

    string word = "";
    while (c >= 0){
        if (temp.at(c) == '0' && f == 0){
            numbers.push_back(stol(word));
            word = "";
            f = 1;
        }
        if (temp.at(c) != '0'){
            word += temp.at(c);
            f = 0;
        }
        if (c == 0 && word.size() != 0){
            numbers.push_back(stol(word));
        }
        --c;
    }
    

    // 소수 판별
    for (long long i = 0; i < numbers.size(); ++i){
        int flag = 0;
        if (numbers.at(i) == 1){
            continue;
        }
        for (long long j = 2; j <= sqrt(numbers.at(i)); ++j){
            if (numbers.at(i) % j == 0){
                flag = 1;
                break;
            }
        }
        if (flag == 0){
            ++answer;
        }
    }
    return answer;
}

- 소수 판별 시 어떤 수의 절반까지 탐색하면 시간 초과가 난다. => 제곱근까지 탐색하기

- n <= 1,000,000이므로, int 자료형을 사용하면 overflow가 생긴다. => 안전하게 long long까지로 늘려주기