讨论/面试考题/中国移动的坑货编程题,这题神仙能做?/
中国移动的坑货编程题,这题神仙能做?

Snipaste_2020-05-13_20-23-36.png
Snipaste_2020-05-13_20-23-56.png

展开讨论
在路上发起于 2020-05-13

这有什么不能做的?很简单啊?
因数是奇素数
当且仅当它是素数的(奇素数-1)次方

数据范围在10^14次方
因此从2次方开始往上遍历
所有素数的2次方在AB之间的
所有素数的4次方在AB之间的
所有素数的6次方在AB之间的
所有素数的10次方在AB之间的
直到2^n大于B
div2 A-C 级别的题
就一点思维量 + 一点点代码量

等一下来写个证明和代码
我写的好像超时了,大概可以通过打表、二分什么的优化,但思路应该就是这样了,不想改了。

# region prime
# 素数模板

class Sieve:
    def __init__(self):
        self._n = 6
        self._list = [2, 3, 5, 7, 11, 13]
    def extend(self, n):
        if n <= self._list[-1]: return
        maxbase = int(n ** 0.5) + 1
        self.extend(maxbase)
        begin = self._list[-1] + 1
        newsieve = [i for i in range(begin, n + 1)]
        for p in self.primerange(2, maxbase):
            for i in range(-begin % p, len(newsieve), p):
                newsieve[i] = 0
        self._list.extend([x for x in newsieve if x])
    def extend_to_no(self, i):
        while len(self._list) < i: 
            self.extend(int(self._list[-1] * 1.5))
    def primerange(self, a, b):
        a = max(2, a)
        if a >= b: return
        self.extend(b)
        i = self.search(a)[1]
        maxi = len(self._list) + 1
        while i < maxi:
            p = self._list[i - 1]
            if p < b:
                yield p
                i += 1
            else: return
    def search(self, n):
        if n < 2: raise ValueError
        if n > self._list[-1]: self.extend(n)
        b = bisect.bisect(self._list, n)
        if self._list[b - 1] == n: return b, b
        else: return b, b + 1
    def __contains__(self, n):
        if n < 2: raise ValueError
        if not n % 2: return n == 2
        a, b = self.search(n)
        return a == b
    def __getitem__(self, n):
        if isinstance(n, slice):
            if n.stop:
                self.extend_to_no(n.stop + 1)
                return self._list[n.start: n.stop: n.step]
            return islice(self, n.start, None)
        else:
            self.extend_to_no(n + 1)
            return self._list[n]
sieve = Sieve()

# endregion prime

# 上面是我的素数模板,平时打表也可以

def MP_Prime(A, B):
    if A > B:
        A, B = B, A
    t = 0
    for p in sieve[1:]:
        p -= 1
        if 2 ** p > B:
            break
        for b in sieve:
            if b ** p > B:
                break
            if b ** p >= A:
                t += 1
    return t

if __name__ == "__main__":
    print(MP_Prime(1, 10 ** 14))
2
展开全部 5 讨论