다항식 시간 알고리즘을 사용하여 숫자 지수가 숫자인지 여부를 테스트 할 수 있습니까?

Question

유명한 종이 PRIMES is in P을 연구하면 혼란스러워집니다.

알고리즘의 첫 단계는 If (n=a^b for nature number a and b>1), output COMPOSITE.입니다. 전체 알고리즘이 다항식 시간으로 실행되므로이 ​​단계도 O (log n)^c에서 완료되어야합니다 (주어진 입력 크기는 O (log n)입니다. 일부 인터넷 검색 후 대상을 공격하기 위해 어떤 알고리즘을 알아낼 수 없습니다

질문 :.?

이 다항식 시간에 다른 수의 번호 지수 여부를 테스트 할 수있는 알고리즘이 있습니까

감사합니다 최고 감사합니다.

Answer 1

≤ 로그 ₂ N B, 우리는이를 테스트하기 log n보다 작은 모든 b 년대 확인할 수 n=a^b 후 (> 1의 경우), 우리는 N 로그 2 내지 b를 찾기 위해 반복 등에 대한 수 a을 찾으면 1..sqrt (n) 사이에서 이진 탐색을 수행해야합니다. 그러나 바이너리 검색은 반복을위한 O (logn) 시간을 필요로하며 마지막으로 검색의 각 단계에서 (확인을 위해 a을 찾음) ^b == n인지 확인해야하며 O (log n)이므로 전체 검색 시간은 O (로그 n) 일 것입니다. 더 빠른 방법이있을 수 있지만 AKS이 O (로그 n)임을 알게되면이 O (로그 3)는 아무런 해를 끼치 지 않습니다.

Answer 2

숫자 n은 b^e = n 인 b와 e가 존재하는 경우 완벽한 힘입니다. 예를 들어 216 = 6^3 = 2^3 * 3^3은 완벽한 힘이지만 72 = 2^3 * 3^2는 그렇지 않습니다. 숫자가 완벽한 힘인지 결정하는 속임수는 숫자가 완벽한 힘이라면 지수 e가 log2n보다 작아야한다는 것입니다. 왜냐하면 e가 더 크면 2^e가 n보다 커야하기 때문입니다. 또한 소수가 복합 지수의 완벽한 힘이라면 복합 요소의 주요 인자에 대한 완벽한 힘이기 때문에 소수를 테스트하는 것만으로 충분합니다. 예를 들어, 2^15 = 32768 = 32^3 = 8^5는 완벽한 큐브 루트이고 완벽한 5 번째 루트입니다. 따라서 알고리즘은 log2 n보다 작은 소수의리스트를 만들고 각각을 테스트하는 것입니다. log2 n이 작고 소수의리스트가 더 작기 때문에 이것은 큰 n의 경우조차별로 효과가 없다.

here 구현을 볼 수 있습니다.

Answer 3

public boolean isPerfectPower(int a) { 
    if(a == 1) return true; 
    for(int i = 2; i <= (int)Math.sqrt(a); i++){ 
     double pow = Math.log10(a)/Math.log10(i); 
     if(pow == Math.floor(pow) && pow > 1) return true; 
    } 
    return false; 
}