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

• 문제 : K진수에서 소수 개수 구하기
  • 간단 요약
    • 규칙
    • 예시
    • 로직
      • 소수 판별
        • 에라토스테네스의 체 간단 요약
      • 진법 변환
      • 전체 코드

문제 : K진수에서 소수 개수 구하기

• 간단 요약

  숫자 N(1 <= N <= 1,000,000)과 진법 K(3 <= k <= 10)이 주어졌을 때 아래의 규칙을 만족하는 소수의 개수를 구하자

  • 규칙

    1. 0P0처럼 소수 양쪽에 0이 있는 경우
    2. P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무 것도 없는 경우
    3. 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
    4. P 처럼 소수 양쪽에 아무것도 없는 경우
    5. P에는 0이 들어가지 않음

  • 예시

    437674을 3진수로 바꾸면 211020101011

    => 211020101011 총 3개가 존재

  • 로직

    숫자를 진법에 맞추어서 변환 후 오른쪽이 0이거나 아무것도 없을 때까지 숫자를 읽고서, 해당 숫자가 소수인지 아닌지 판별해서 소수라면 answer를 증감!

    • 소수 판별

      반드시 시간 복잡도 때문에 에라토스테네스의 체라는 수학을 이용해야 함

        bool isPrimeNumber(long long num){
            if(num == 1){return false;}
            for(long long i = 2; i*i <= num; i++){
                if(num % i == 0){
                    return false;
                }
            }
            return true;
        }
      

      • 에라토스테네스의 체 간단 요약

        특정 숫자 N의 소수 유무를 파악하고 싶을 때,

        이의 제곱근에 해당하는 수까지만 나누어보면서 안나눠지는 것이 확인되면 무조건 소수

    • 진법 변환

      숫자를 진법에 맞추어서 바꾸는 방법은 숫자 N을 계속해서 K로 나눈 나머지가 앞으로 위치하면서 N을 K로 나누어서 N이 0이 될 때까지 반복

        if(k != 10){
           while(n != 0){
                int x = n % k;
                n /= k;
                char result = ('0' + x);
                num = result + num;
           }
        }
        else{
            num = to_string(n);
        }
      

    • 전체 코드

        #include <string>
        #include <vector>
        #include <cmath>
      
        using namespace std;
      
        bool isPrimeNumber(long long num){
            if(num == 1){return false;}
            int erasNumber = log2(num);
      
            for(long long i = 2; i*i <= num; i++){
                if(num % i == 0){
                    return false;
                }
            }
            return true;
        }
      
        int solution(int n, int k) {
            string num;
            int answer = 0;
            if(k != 10){
                while(n != 0){
                    int x = n % k;
                    n /= k;
                    char result = ('0' + x);
                    num = result + num;
                }
            }
            else{
                num = to_string(n);
            }
            string tmp;
            for(int i = 0; i < num.length(); i++){
                if(num[i] == '0'){
                    tmp = "";
                    continue;
                }
                tmp += num[i];
                if(i+1 >= num.length() || num[i+1] == '0' ){
                    if(tmp != "" && isPrimeNumber(stoll(tmp))){
                    answer++;
                    }
                tmp="";
                }
            }    
            return answer;
        }