@article{aea9779cf7ac44c6b0d86937bd5e00ee,
title = "Sieve Algorithms for Perfect Power Testing",
author = "Eric Bach and Sorenson, {Jonathan P}",
note = "A positive integern is a perfect power if there exist integersx andk, both at least 2, such thatn=x k . The usual algorithm to recognize perfect powers computes approximatekth roots fork≤log 2 n, and runs in time O(log3 n log log logn).First we improve this worst-case running time toO(log3 n) by using a modified Newton's method to compute approximatekth roots.",
year = "1993",
month = apr,
doi = "10.1007/BF01228507",
language = "American English",
volume = "9",
journal = "Algorithmica",
issn = "0178-4617",
}