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

1.문제 링크

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

2. 풀이 전 계획과 생각

• 수학적 지식 이용

3. 풀이

#include <string>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;

bool isprime(long n){
    if(n <= 1) return false;
    else if(n == 2) return true;
    for(int i = 2; i <= sqrt(n); i++)
        if(n % i == 0) 
            return false;
    return true;
}

int solution(int n, int k) {
    string str = "";
    
    // n을 k진수로 바꾸기 
    while(n > 0) {
        str = to_string(n % k) + str;
        n /= k;
    }     
    
    int answer = 0;
    int i;
    for(i=0;i<str.size();){
        if(str[i]=='0') {
            i++;
            continue;
        }
        int cnt=1;
        for(int j=i+1; j<str.size(); j++){
            if(str[j]=='0') break;
            cnt++;
        }
        if(isprime(stol(str.substr(i, cnt)))) answer++;
        i+=cnt;
    }
    
    return answer;
}

우선 주어진 수 n을 k진법으로 바꾼다.

바꾼후 문제의 조건으로 문자열을 잘라 그 문자열을 isprime함수를 통해 소수인지 아닌지를 판별한다.

4. 풀이하면서 고민했던 점

5. 문제를 풀고 알게된 개념 및 소감

• n을 k진수로 바꾸는 방법을 알게됨.

• 소수인지 아닌지 판별하는 방법을 알게됨.