Hueestory

[2022 KAKAO BLIND] - k진수에서 소수 개수 구하기 (C++) 본문

PS(중단)/programmers

[2022 KAKAO BLIND] - k진수에서 소수 개수 구하기 (C++)

히명 2024. 8. 27. 15:10
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

bool isPrime(long long num){
    if (num < 2) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;
    
    for (long long i = 3; i <= sqrt(num); i += 2)
        if (num  % i == 0) return false;
    
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    string s = "";
    
    while (n > 0){
        s += to_string(n % k);
        n /= k;
    }
    reverse(s.begin(), s.end());
    string tmp = "";
    
    for(char x : s){
        if(x == '0'){
            if(!tmp.empty() && isPrime(stoll(tmp)))
                answer++;
            tmp = "";
        }
        else tmp += x;
    }
    
    if (!tmp.empty() && isPrime(stoll(tmp)))
        answer++;
        
    return answer;
}

 

1. 주어진 수를 k진수로 변환

- n을 k로 나눈 나머지 값이 k진수로 들어갈 값, n을 k로 나눈 값을 n에 다시 저장

 

2. 변환된 수를 string으로 변환하고 0을 기준으로 나눔

- string tmp;의 경우 tmp.empty()는 tmp가 비어있는지를 판단하는 bool

- stol : string to long

- stoll : string to long long

 

3. 소수 판별 함수에 넣고 판별 후 answer 갯수에 추가


Comments