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

문제

 

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

프로그래머스

문제풀이

 

복잡해 보여도 간단한 문제이다.

숫자를 k진수로 바꾸고, 0을 기준으로 나누어서 해당 숫자가 소수인지만 판별하면 된다.

10진수의 범위는 10^6이므로 다른 진수로 바꿨을 때 에라토스테네스체를 쓰기엔 범위가 커 보여서 숫자마다 판별하기로 했다.

 

먼저 숫자를 입력받으면 나머지 연산, 나누기를 통해 숫자를 string형태로 바꾸고 reverse를 이용해 뒤집는다.

그다음 istringstream, getline을 통해 '0'을 기준으로 문자열을 나눈다.

나눈 문자열을 stoll을 통해 long long형태로 바꾸고 2부터 나누어 나머지가 0이 되는지를 판별한다.

숫자가 1일 때는 넘어간다.

 

소수이면 ++answer을 한다.

 

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#define ll long long
using namespace std;

int solution(int n, int k) {
    int answer(0);
    string num("");
    while (n > 0) {
        num += to_string(n % k);
        n /= k;
    }

    reverse(num.begin(), num.end());

    istringstream iss(num);
    string substr("");

    while (getline(iss, substr, '0')) {
        if (substr.empty()) continue;
        ll subnum(stoll(substr));
        bool flag(false);
        if (subnum == 1) continue;
        for (ll idx = 2; idx * idx <= subnum; ++idx) {
            if (subnum % idx == 0) {
                flag = true;
                break;
            }
        }
        if (flag == false) {
            ++answer;
        }
    }

    return answer;
}