Carmichael函数未递增k问题：输入任意n均返回0

核心问题拆解 #

1. k初始值错误导致直接返回0
   任何数的0次方结果都是1，所以coprime^0 % n必然等于1。代码中k初始化为0，第一次循环就触发return k，完全没机会执行k递增逻辑。而Carmichael函数要求的是最小正整数k，所以k必须从1开始初始化。

2. k的递增位置逻辑完全错误
   原代码把k = k+1放在return k之后，这条语句永远不会被执行。同时，原逻辑只要第一个互质数满足条件就直接返回，不符合Carmichael函数的定义——必须所有与n互质的数都满足x^k ≡ 1 mod n，才能返回当前k；否则需要k递增后重新验证所有数。

修复后的完整代码 #

function gcd(a, b)
  if b == 0 then
    return a
  else
    return gcd(b, a % b)
  end
end

function carmichael(n)
  local coprimes = {} -- 使用局部变量避免全局污染
  for i = 1, n-1 do
    if gcd(i, n) == 1 then
      table.insert(coprimes, i)
    end
  end
  
  -- 特殊情况处理：n=1时无互质数，按定义返回1
  if #coprimes == 0 then
    return 1
  end

  local k = 1 -- 从正整数1开始初始化
  while true do
    local all_valid = true
    -- 遍历所有互质数，验证当前k是否满足条件
    for _, coprime in ipairs(coprimes) do
      if (coprime ^ k) % n ~= 1 then
        all_valid = false
        break
      end
    end
    -- 所有互质数都满足条件时返回k，否则k递增继续循环
    if all_valid then
      return k
    end
    k = k + 1
  end
end

input = io.read()
print(carmichael(tonumber(input)))

额外优化说明 #

• 将coprimes和k改为局部变量，符合Lua的最佳实践，避免全局变量冲突。
• 增加了n=1的特殊情况处理，避免空列表导致的逻辑异常。

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