[프로그래머스][level2] k진수에서 소수 개수 구하기 (C++)

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

코딩테스트 연습 - k진수에서 소수 개수 구하기

 

 

[난이도] level2
[유형] 구현

[풀이]
n을 k진법으로 변환 시켜준 뒤, 0을 기준으로 나눠지는 모든 수에 대해 소수인지 판별해서
소수인 것의 개수를 구해주면 됩니다.

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
bool isPrime(ll v){
    if(v==1) return false;
    for(ll i=2;i<=sqrt(v);i++){
        if(v%i==0) return false;
    }
    return true;
}
int solution(int n, int k) {
    int answer = 0;
    string s;
    while(n/k>0){
        int m = n%k;
        s+=m+'0';
        n/=k;
    }
    s+=n+'0';
    reverse(s.begin(),s.end());
    for(int i=0;i<s.size();i++){
        if(s[i]=='0') continue;
        string t;
        int j=i;
        for(;j<s.size()&&s[j]!='0';j++) t+=s[j];
        i=j;
        answer+=isPrime(stol(t));
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/k진수에서_소수_개수_구하기.cpp