小编Lak*_*man的帖子

我正在尝试这个问题一段时间但一次又一次地得到错误的答案.数字可能非常大<= 2 ^ 2014. 22086. Prime Power Test

关于我的算法的说明:

1. 对于给定的数字,我正在检查该数字是否可以表示为主要权力的形式.
2. 因此,检查主要功率的最大限制是log n base 2.
3. 最后问题减少到找到一个数字的第n个根,如果它是素数,我们有我们的答案,否则检查所有i直到log (n base 2)和exit.
4. 我已经使用了各种优化并测试了大量的测试用例,并且我的所有算法都给出了正确的答案
5. 但是法官说错了答案.
6. Spoj有另一个类似的问题,小约束n <= 10 ^ 18,我已经接受了Python和C++(c ++中的最佳解算器)

这是我的python代码请建议我,如果我做错了我不是很精通python所以我的算法有点冗长.提前致谢.

我的算法:

import math
import sys
import fractions
import random
import decimal
write = sys.stdout.write
def sieve(n):
    sqrtn = int(n**0.5)
    sieve = [True] * (n+1)
    sieve[0] = False
    sieve[1] = False
    for i in range(2, sqrtn+1):
        if sieve[i]:
            m = n//i - i
            sieve[i*i:n+1:i] = [False] * (m+1) …