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

문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/92335

point 1. int 형식 사용시 범위를 벗어남 > long 사용
point 2. 소수 판별시 i < n 까지 돌 필요가 없이 n제곱근까지만 판별하면 됨 n까지 돌릴경우 시간초과 이슈 발생 (+n제곱근의 정수형에 +1까지 해줘야함 int로 변경하면서 생기는 오차고려)
point 3. while문에서 마지막에 나온 소수판별에 쓰일 값은 반환하기 전 마지막으로 체크해줘야함

using System;

public class Solution {
    public int solution(int n, int k) {
        int calnum = n;
        int answer = 0;
        int maxval = 0;

        while (calnum > Math.Pow(k, maxval))
        {
            maxval++;
        }
        answer = ChangePrimeNum(maxval - 1, k, calnum);


        return answer;
    }
    public bool CheckPrime(long n)
    {
        if (n == 2)
        {
            return true;
        }
        if( n == 1)
        {
            return false;
        }
        for (int i = 2 ; i < (int)Math.Sqrt(n)+1 ; i++)
        {
            if(n % i == 0)
            {
                return false; 
            }
                           
        }
        
        return true;
    }
    public int ChangePrimeNum(int maxval ,int k, int calnum)
    {
        string changenum = "";
        int returnval = 0;
        while (maxval >= 0)
        {
            int val = 0;

            while (calnum - Math.Pow(k, maxval) >= 0)
            {
                calnum = calnum - (int)Math.Pow(k, maxval);
                val++;
            }
            maxval--;
            if(val != 0 )
            {
                changenum += val.ToString();
            }
            else
            {
                if (changenum != "")
                {
                    if (CheckPrime(Convert.ToInt64(changenum)))
                        returnval++;

                    changenum = "";
                }
            }
        }
        if ( changenum != "")
        {
            if (CheckPrime(Convert.ToInt64(changenum)))
                returnval++;
        } 
        return returnval;
    }
}