C++ 中的 Legendre 定理：概念、算法、实现

勒让德猜想是一个陈述，指出在两个连续的自然数平方之间总是存在一个素数。在本文中，我们将讨论勒让德猜想及其算法和实现。

数学陈述

在任意两个数n^2和(n+1)^2之间存在一个素数p。在这种情况下，n是一个整数。猜想是一个没有数学证明的结论。因此，勒让德猜想不需要数学证据。

问题陈述

对于给定的数字n，我们将打印从1到n之间，每个n^2到(n+1)^2范围内的素数。

方法

• 首先，创建一个名为count的变量来跟踪素数列表。
• 启动一个循环 for(i=1;i<n;i++)。
• 之后，重复外部循环，从 j = i^2 到 j = (i+1)^2。
• 对于每个 j，通过将其除以从2到 j 的平方根的数字来检查它是否是素数。
• 如果 j 是素数，则增加 count 中的值。
• 打印 i 的 count。

示例 1

让我们举一个例子来说明C++中的勒让德猜想。

文件名：Legendre's.cpp

输出

 
The Value of the number m: 5
For i: 1 Total prime numbers in the following range 1 and 4 = 2
For i: 2 Total prime numbers in the following range 4 and 9 = 2
For i: 3 Total prime numbers in the following range 9 and 16 = 2
For i: 4 Total prime numbers in the following range 16 and 25 = 3
For i: 5 Total prime numbers in the following range 25 and 36 = 2
For i: 6 Total prime numbers in the following range 36 and 49 = 4
For i: 7 Total prime numbers in the following range 49 and 64 = 3
For i: 8 Total prime numbers in the following range 64 and 81 = 4   

说明

• 该代码解释了勒让德猜想，这是一个数论假设。
• 它由三个函数组成：key、legendre_notion 和 principal。主要函数找到素数m，其因子从2到m的平方根。之后，它返回m是否为素数。值得注意的是，通常它将1分配给非素数的角色。
• 名为legendre_concept的函数接收整数i，并从1迭代到i。每次迭代执行两个操作：i^2和(i+1)^2。该算法通过调用素数函数来计算两个平方之间有多少个素数。计数存储在总变量中，结果打印到控制台。
• 主函数包含m=8的初始化。此m值作为参数传递给legendre_concept函数，然后将m的值打印到控制台。
• 执行代码后，将显示从1到8的连续整数平方之间的素数结果。

示例2：高效方法

让我们再举一个例子来说明C++中的勒让德猜想

文件名：Legendre's2.cpp

输出

 
The Value of the number is:  10
For i: 1 Total primes in the range 1 and 4 = 2
For i: 2 Total primes in the range 4 and 9 = 2
For i: 3 Total primes in the range 9 and 16 = 2
For i: 4 Total primes in the range 16 and 25 = 3
For i: 5 Total primes in the range 25 and 36 = 2
For i: 6 Total primes in the range 36 and 49 = 4
For i: 7 Total primes in the range 49 and 64 = 3
For i: 8 Total primes in the range 64 and 81 = 4
For i: 9 Total primes in the range 81 and 100 = 3
For i: 10 Total primes in the range 100 and 121 = 5   

说明

• 代码通过导入所需的头文件并声明一个常量数字“size”来限制素数的搜索范围，该范围为10001。
• 函数“findPrimes”使用埃拉托斯特尼筛法找到所有小于“size”的素数。它将每个素数的倍数分类为非素数，并维护向量“primes”中非素数的计数。
• 在主函数中，调用函数“findPrimes”来填充“primes”向量中的素数计数。
• 之后，循环从1运行到“num”，对于每次迭代，将“init”和“last”范围值计算为ii和(i+i+1)。
• 调用操作“countPrimesInRange”以确定此范围内的素数数量。

结论

总之，勒让德猜想是一个令人兴奋的数学猜想，它指出在自然数的连续平方之间至少存在一个素数。每个实验都通过简单地确定这些数字平方范围内的整数素数来作为假设的实际证明。

由埃拉托斯特尼筛法优化的实现，在num值较大时，大大加快了朴素策略的速度。尽管勒让德猜想尚未被证明，但实现的发展提供了在可用计算约束下验证它的实用工具。