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 个问题：

不管你有多少测试用例，你都会重复同样的任务，这是浪费时间和资源
你离开unchanged/ignore上面的numbers/primesint(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)的素数个数，其他2点简单fix

我会把它放在它自己的函数中，这样更容易重用和玩，而且对于计数部分，你怎么做没有问题，但是用 [=18 更方便=] 一次进行所有计数

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)

计数器仍然更好，因为只需一次即可获得所有答案，如果需要，您可以使用普通词典制作自己的答案，但我将其作为练习留给 reader。

10^6 以内的最小质因数 n 有多少个？

How many numbers have n as their smallest prime factor within 10^6?

python

sieve-of-eratosthenes