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

tose33 2022. 2. 2. 15:56

코딩테스트 연습 - k진수에서 소수 개수 구하기

문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소

programmers.co.kr

stringstream과 getline 함수를 이용해 '0'을 구분자로 해서 조건에 맞는 수들을 구한다.

예를들어 k진수로 변환한 결과가 211020101011 이라면 '0'으로 구분해서 각각의 수들을 때어낸다.

211

결과적으로 위와 같은 숫자들이 나오는데, 이제 이 숫자들이 소수인지 아닌지만 판단하면 된다.

소수를 구할때 에라토스테네스의 체를 이용할까 생각했지만 k진수로 변환한 결과가 최대 몇자리가 될지 가늠이 안되서 그냥 일일히 소수인지 판단해줬다.

n이 소수인지 판단은 그냥 2부터 수를 올리며 나눠떨어지는지 보면되는데

만약 n-1까지 나눠보게 되면 시간초과가 난다.

소수를 판단할때는 n의 루트까지만 나눠보면 알 수 있다. (소수 판별 알고리즘인 에라토스테네스의 체 참고)