거듭제곱 판별법

1. 2의 거듭제곱
2. 소수 p의 거듭제곱
3. 4의 거듭제곱

 

 

1) 2의 거듭제곱

n > 0 && (n & (n-1)) == 0

• 2의 거듭제곱(1, 2, 4, 8, …)은 이진수로 0001, 0010, 0100, 1000 형태
  = 이진수 표현에서 2의 거듭제곱은 항상 1개의 비트만 켜져 있음
• 따라서 n과 n-1은 공통 비트가 없음 → n & (n-1) == 0

---

2) 소수 p의 거듭제곱

가정: 어떤 소수 p에 대하여 표현 가능한 최대 거듭제곱을 p^k

 

다음 식이 성립하면 n은 반드시 p의 거듭제곱이다.

n > 0 && (p^k % n == 0)

 

이유

• p^k는 소수 p의 순수 거듭제곱이므로
• p^k의 약수는 오직 1, p, p^2, …, p^k
• 따라서 p^k를 나눌 수 있는 수는 p의 거듭제곱 외에는 없다

소수 p	최대 거듭제곱 (int 범위)	판별식
2	2^30 = 1,073,741,824	n > 0 && 1073741824 % n == 0
3	3^19 = 1,162,261,467	n > 0 && 1162261467 % n == 0
5	5^13 = 1,220,703,125	n > 0 && 1220703125 % n == 0
7	7^11 = 1,977,326,743	n > 0 && 1977326743 % n == 0

---

3) 4의 거듭제곱 

n > 0 && (n & (n-1)) == 0 && n % 3 == 1

• 4의 거듭제곱은 2의 거듭제곱 중에서 n % 3 == 1인 값들

예시

• 4 % 3 = 1
• 16 % 3 = 1
• 64 % 3 = 1