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

[python 알고리즘 팁] 소수판별, 진수 변환

소수 판별 64까지의 약수를 판별하자면 1 x 64, 2 x 32x 4 x 16, 8 x 8로 1, 2, 4, 8, 16, 32, 64의 약수를 갖는걸 알 수 있다 자기 자식의 제곱근까지의 수를 살펴보면 전체 약수를 구할 수 있다. 이렇게 소수를 찾는 방법을 에스테라토스 체라 한다. num(num > 0)이 주어졌을 때 소수인지 아닌지 판별하려면 1이면 소수가 될 수 없다 2이면 소수다 짝수면 2로 나눠지므로 소수가 아니다 그 외 수는 홀수만 살펴보면서 num과 나누었을 때 나머지가 0인 수가 있다면 num은 소수가 아니다 위와 같은 조건들로 코드를 짜면 아래와 같다 import math # 소수 판별 함수 def check(num): # 2이면 소수 if num == 2: return True # 1이..