有多少个数在10^6内以n作为其最小素数因子？

Question

for _ in range(int(input())):
    n=int(input())
    least_prime = [0] * (1000001)
    count=0
    for i in range(2, int(1000001**0.5 + 1)): 
 
        if least_prime[i] == 0:
            least_prime[i] = i 

            for j in range(i * i, 1000000, 2*i) : 
                if (least_prime[j] == 0) : 
                    least_prime[j] = i 
    
    for i in range(2, 1000001) : 
        if least_prime[i] == n:
            count+=1
    print(count)

谁能降低问题的时间复杂性？也许试了一个小时，但再简单不过了。 第一个for loop是测试用例的数量问题是关于有多少个数在10^6内以n作为它们的最小素数因子？

Answer 1

您的代码有3个问题：

• 无论有多少测试用例，您都要重复相同的任务，这是浪费时间和资源的
• 保持不变/忽略上面的数字/素数int(1000001**0.5 + 1)
• 在你的j范围内做一个2*i的步骤，你会错误地标记一组数字，比如6，它应该把2标记为它的最小素数，但是它被标记为它自己，因为它被跳过了，6=4+2，但是你永远不会得到你的j范围，因为你做了一个4的步骤，所以你得到了4,8,12，。。。而不是4,6,8

如何修复它？简单，首先只做一次筛子，不需要重复完全相同的事情10**6次，或者不管你有多少个测试用例，两个或更多都是两次太多（如果n始终是素数，即78498，这是素数小于10**6），另外两个点是简单的修复

我会把它放在它自己的函数中，这使它更易于重用和使用，对于计数部分，如何操作没有问题，但是使用一个^{}可以更方便地同时进行所有计数

from collections import Counter

def make_sieve(MAX):
    MAX += 1
    least_prime = [0] * MAX
    for i in range(2, MAX): 
        if least_prime[i] == 0:
            least_prime[i] = i 
            for j in range(i * i, MAX, i) : 
                if (least_prime[j] == 0) : 
                    least_prime[j] = i
    return least_prime

result = Counter(make_sieve(10**6))

print("n=2->",result[2])# n=2-> 500000
print("n=3->",result[3])# n=3-> 166667

所以现在你的测试可以简单到

for _ in range(int(input())):
    n = int(input())
    print(result[n])

为了完整起见，这里是如何不用计数器就能完成的

least_prime = make_sieve(10**6)
for _ in range(int(input())):
    n = int(input())
    count = 0 
    for p in least_prime: 
        if p==n:
            count+=1
    print(count)

但这也太长了，一个列表已经为我们提供了.count

least_prime = make_sieve(10**6)
for _ in range(int(input())):
    n = int(input())
    count = least_prime.count(n)
    print(count)

计数器更好，因为你只需一次就可以得到所有答案，如果需要的话，你可以用一本普通字典自己编一本，但我把它作为练习留给读者