题目链接

最小质因子之和(Easy Version) - 蓝桥云课 (lanqiao.cn)

解题思路

查询 $T$ 次 $2$ 到 $N$ 每个数的最小质因数之和

线性筛 + 前缀和

本题我们首先需要找到能够最快求出 $2$ 到 $N$ 每个数最小质因数的算法，然后对于重复的查询质因数之和只需要用前缀和维护确定直接输出即可。

线性筛是一种线性复杂度的快速算法，
一种比常规欧拉筛更简便的实现。

# -*- coding: utf-8 -*-
# @Author : BYW-yuwei
# @Software: python3.8.6
def linear_sieve(n):is_prime, primes = [True] * (n + 1), []for p in range(2, n + 1):if is_prime[p]:primes.append(p)for i in range(p * p, n + 1, p):is_prime[i] = Falsereturn primes

线性筛的思想是让每个合数只被其最小质因数筛去一次，这里对于每个素数，筛去其不小于其平方，不大于上界的所有倍数。
1、首先初始化判断素数列表为真，最小质因数列表为0。
2、循环中未被标记的数为素数，显然其最小质因数为本身。
3、在素数条件下，将不小于其平方，不大于上界的所有倍数标记。
4、即同一个数仍然有可能被重复选中，仅在其未被筛过（最小质因数为初始值）时将其最小质因数赋值为该素数。
最后返回最小质因数列表。并计算存储其前缀和。

时间复杂度为 $O(N+T)$。

AC_Code

python程序：

# -*- coding: utf-8 -*-
# @Author : BYW-yuwei
# @Software: python3.8.6
def sieve(n):is_prime = [True] * (n + 1)factors = [0] * (n + 1)for p in range(2, n + 1):if is_prime[p]:factors[p] = pfor i in range(p * p, n + 1, p):is_prime[i] = Falseif factors[i] == 0:factors[i] = preturn factorsif __name__ == '__main__':N = int(3e6)factors = sieve(N)s = [0] * (N + 1)for i in range(2, N + 1):s[i] = s[i - 1] + factors[i]for _ in range(int(input())):n = int(input())print(s[n])