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

https://school.programmers.co.kr/learn/courses/30/lessons/92335?language=cpp

프로그래머스

 

0으로 split 작업을 하고 소수를 판별하는 문제이다.

소수판별에는 여려가지 방법이 있다.

 

1. O(N)이 걸리는 가장 기본적인 방법

2. 에라토스테네스의 체

3. 오일러의 체

 

오일러의 체는 정말 코드포스같은 경쟁적 프로그래밍에서 필요하지만, 여기선 이렇게까지 딥하게 소수를 찾을 필욘 없다. 비효율적이다.

https://ps.mjstudio.net/linear-sieve 

PS를 위한 수학 - Linear Sieve(오일러의 체)

하지만 알고 싶다면 이 블로그를 추천한다.

 

에라토스테네스의 체는 나도 포스팅했었던 방법이다. 

 

bool Era (int n){
	if(n < 2) return false;
    
    for(int i = 2; i * i <= n; i++) {
    	if(n % i == 0) return false;
    }
    
	return true;
}

 

위 방법을 사용하면 아래처럼 코드를 짤 수 있다. 1번에서 계속 시간초과가 났는데 에라토스테네스 부분에서 i를 int로 해서 그랬던 거였다

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

string trans(int N, int K){
    string res = "";
    
    while(N > 0){
        res += ((N % K) + '0');
        N /= K;
    }
    
    reverse(res.begin(), res.end());
    
    return res;
}

bool check(string n){
    if(n == "") return false;;
    
    long long num = stol(n);
    if(num < 2) return false;
    
    for(long long i = 2; i * i <= num; i++){
        if(num % i == 0) return false;
    }

    return true;
}

int solution(int n, int k) {
    int answer = 0;
    
    string number = trans(n, k);
    string tmp = "";
    for(int i = 0; i < number.size(); i++){
        if(number[i] == '0'){
            if(check(tmp)) answer++;
            tmp = "";
        }
        
        tmp += number[i];
    }
    if(check(tmp)) answer++;
    
    return answer;
}