C++ Wilson 定理

威尔逊定理指出，一个数可以根据阶乘和模算术的性质被认为是素数，这符合数学思想。它由数学家约翰·威尔逊提出，并由约瑟夫-路易斯·拉格朗日证明。它指出：

对于正整数 p>1：(p-1)!≡-1(mod p)。该引理间接指出，如果 p 是一个素数，则对于 p > 1，-(p-1)! mod p 必须存在。此外，如果 p 不是素数，则 (p-1)!≡-1 mod p。

威尔逊定理是理解素数的一个有用的理论工具，但由于阶乘数值的快速增长，计算大 p 的阶乘是不切实际的。尽管如此，威尔逊定理仍然是数论中理解模算术中数性质重要性的基石。

替代技术有：

• 埃拉托斯特尼筛法：有效生成特定限制以下的所有素数。
• 概率素性测试：像米勒-拉宾测试这样的技术，通常被认为是为大整数提供高效素性查找的方法。

威尔逊定理的理论重要性

尽管效率低下，但从数论的角度来看，威尔逊定理具有重要的历史意义；它提供了以下内容：阶乘和素数之间的直接联系以及素数的独特模性质。对模算术的深刻理解，这是密码学等领域的基础。从历史背景来看，威尔逊定理仍然是最早对素性提出正式、明确条件的成果之一。

• 阶乘表示：阶乘 (p-1)! 表示从 1 到 p-1 的所有整数的乘积。
• 素数条件：在模 p（其中 p 是素数）下，余数 1, 2, ..., p-1 构成一个完整的剩余系，使得每个元素都有一个明确且唯一的逆。
• 模运算结果：关系 (p-1)!≡-1(mod p) 基本上意味着，当计算从 1 到 p-1 的所有数的乘积并除以素数 p 时，模运算确实返回 -1。

威尔逊定理如何工作？

• 素数：该定理提供了一种检查素数的方法，并且可以提供比暴力试除法更快的替代方案。
• 阶乘：阶乘随着数字的增加而迅速增长，计算大阶乘的模 n 运算在计算上非常昂贵。因此，该定理通过模算术处理阶乘。
• 计算复杂度：威尔逊定理更为复杂，因为计算大数的阶乘并非易事。尽管如此，该定理在理解数学概念或处理选定的模应用时仍然是一个有用的工具。

模运算和阶乘

在本文中，我们将使用模算术与阶乘。给定 (n-1) 的双阶乘，我们计算双阶乘模 n，并检查它是否等于 n-1。由于数字巨大，对于大 n 的此计算变得非常困难。

威尔逊定理的优点

• 数学洞察力：威尔逊定理揭示了素数的性质，阐明了阶乘与素数之间的关系。
• 验证素性：该定理为测试数字是否为素数提供了明确的条件；尽管计算昂贵，但它对于验证较小的素数是可靠的。
• 教学工具：威尔逊定理可以在课堂上用作教学方法，以引入模算术和素数性质，为学生提供数论和素数行为的洞察力。

威尔逊定理的缺点

• 对大数效率低下：计算大数的阶乘会使复杂度急剧增加。
• 实际使用的替代方法：存在高效的算法，例如米勒-拉宾素性测试和 AKS 素性测试，它们是为实际应用中非常大数的素性测试而创建的。
• 计算限制：在 C++ 等语言中，处理模运算中的大阶乘往往会导致溢出，其中 int 的大小是有限的。这限制了威尔逊定理在竞争性编程和实践中的适用性。

示例

让我们举一个例子来说明 C++ 中的威尔逊定理。

输出

 
Please enter the number: 45
45 is not a prime number from the  Wilson's Theorem.   

说明

此程序从用户获取一个数字，并使用威尔逊定理检查它是否为素数。威尔逊定理指出，当且仅当 (p-1)!≡-1(mod p) 时，数字 p>1 才是素数。

• factorial_modulas 函数
  此函数计算 num (即 p-1) 的阶乘模 p，以使计算可行并避免溢出。它使用循环将 1 到 num 的数字相乘，并在每次乘法时取模 p。
• isPrime_WilsonNumber 函数
  此函数使用威尔逊定理检查 p 是否为素数。如果 p <= 1，则返回 false，因为它不是素数。对于 p = 2，它返回 true（因为 2 是唯一一个偶素数）。对于 p 的任何其他值，它计算 (p-1)! % p，并检查 fact(p-1)+1 % p == 0，在这种情况下我们可以说该数字是素数。
• 主函数
  main 函数获取用户输入，使用辅助函数应用威尔逊定理，并打印出该数字是否为素数。

结论

总之，威尔逊定理是使用阶乘的模性质对素数进行数学检验的最简单方法。它不是一种有效的方法，因为阶乘值对于大数增长得如此之快，但它是数论的一个奇妙性质，说明了素数和模算术的相互关联性。不幸的是，由于其计算复杂性，该定理在实践中对于确定数字是否为素数并不特别有用，但它在学习素数特征和模同余测试方面具有巨大的教学价值。对于更大规模的计算，埃拉托斯特尼筛法或概率素性测试（如米勒-拉宾）是更快速的方法。威尔逊定理将始终因其简洁性和在明确定义素数方面的历史意义而占有一席之地。