[Level_2 / C++ / 카카오] k진수에서 소수 개수 구하기

1. 10진수로 주어진 숫자를 k진수로 변환후 문자열로 저장

2. 소수를 담을 long long 타입의 벡터 생성 후 문자열에서 숫자에 해당되는 부분들을 담기. 

3. 소수인지 아닌지 판단하는 함수 호출 

 

"2 ~ 루트(n)" 에 해당하는 값으로 n을 나눈다.

나누어진다면 false 반환
그렇지 않다면 true 반환

소수 판별법, 왜 루트 N 이하의 수만 나눠보면 되는 것일까?

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
typedef long long ll; 
bool is_prime(ll n) {
    if(n < 2) return false;
    for(int i=2; i<=sqrt(n); ++i) {
        if(n % i == 0) return false;
    }    
    return true;
}
int solution(int n, int k) {   
    int answer = 0;
    string s=""; int prev=0; 
    while(n){
        s+=(n%k)+'0';  
        n/=k; 
    }
    reverse(s.begin(),s.end());
    cout << s << endl;
    string temp ="";
    vector <ll> prime;
    for(int i=0; i<s.size(); i++){
        if(s[i]>='1'&&s[i]<='9')temp+=s[i];         
        else{
            if(!temp.empty()){
                prime.push_back(stoll(temp)); 
                temp=""; 
            }
        }
    }
    if(temp.size())prime.push_back(stoll(temp));     
    for(int i=0; i<prime.size(); i++) if(is_prime(prime[i])) answer++ ;      
    return answer;
}

 

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