技术问询：求1到N中各数的最大非M整除数之和

首先我们明确问题：给定正整数N和M，要计算1到N中每个数的最大不被M整除的除数的总和。比如你提到的例子：N=10、M=3时，各数对应的结果是[1,2,1,4,5,2,7,8,1,10]，总和为41。

下面分两种情况给出解决方案：

情况1：M是质数 #

当M为质数时，我们可以用递归公式高效计算，时间复杂度为O(log_M N)，因为每次递归的参数都会快速缩小到0。

核心思路 #

对于每个数x：

• 如果x不被M整除，它的最大非M整除数就是x本身；
• 如果x被M整除，我们可以把x写成x = M * k，此时x的最大非M整除数等于k的最大非M整除数（因为M是质数，去掉所有M的因子后得到的数一定不被M整除，且是最大的符合条件的除数）。

基于这个思路，我们可以推导出递归公式：
设S(N)为区间[1,N]的结果总和：

1. 边界条件：当N=0时，S(N)=0；
2. 计算k = N // M（即1到N中M的倍数的个数）；
3. 不被M整除的数的总和 = 1到N的总和 - M的倍数的总和，即N*(N+1)//2 - M*k*(k+1)//2；
4. 被M整除的数对应的结果总和等于S(k)；
5. 最终S(N) = 不被M整除的数的总和 + S(k)。

代码实现（Python） #

def max_non_divisible_sum_prime(N, M):
    if N == 0:
        return 0
    k = N // M
    # 计算不被M整除的数的总和
    non_multiple_sum = N * (N + 1) // 2 - M * k * (k + 1) // 2
    # 递归计算被M整除的数对应的结果总和
    return non_multiple_sum + max_non_divisible_sum_prime(k, M)

验证你的例子：

print(max_non_divisible_sum_prime(10, 3))  # 输出41，与示例一致

情况2：M是合数 #

当M为合数时，没有像质数那样简洁的递归公式，我们可以根据N的大小选择不同的方法：

方法1：迭代计算（适合N较小的场景） #

遍历1到N的每个数，对每个数直接找到它的最大非M整除数：

• 如果x不被M整除，直接加x到总和；
• 如果x被M整除，从x//2开始向下遍历，找到第一个能整除x且不被M整除的数，这就是最大的符合条件的除数。

代码实现（Python） #

def find_max_non_divisor(x, M):
    if x % M != 0:
        return x
    # 从x的一半开始往下找最大的符合条件的除数
    for d in range(x//2, 0, -1):
        if x % d == 0 and d % M != 0:
            return d
    return 1  # 极端情况：x是M的幂次，比如x=4、M=4，此时最大除数是1？不对，哦x=4的最大非4整除数是2，这个循环会找到2，所以这个return 1是兜底

def max_non_divisible_sum_composite(N, M):
    total = 0
    for x in range(1, N+1):
        total += find_max_non_divisor(x, M)
    return total

验证示例：N=8、M=4时，各数的结果是[1,2,3,2,5,6,7,2]，总和为28：

print(max_non_divisible_sum_composite(8, 4))  # 输出28，正确

方法2：数学优化（适合N较大的场景） #

如果N很大（比如1e6以上），迭代法效率不够，可以通过质因数分解优化：

1. 先分解M的质因数：M = p1^e1 * p2^e2 * ... * pn^en；
2. 对于每个被M整除的x，找到x中所有M的质因子的指数，然后通过去掉最少的因子，得到最大的不被M整除的除数。
   这个方法需要预处理最小质因数表来快速分解每个数的质因数，实现起来相对复杂，但效率极高。

总结 #

• 当M是质数时，优先使用递归公式，计算速度极快；
• 当M是合数时，小N用迭代法足够，大N可以考虑质因数分解优化的方案。

内容的提问来源于stack exchange，提问作者logan