C++ 哈代-拉马努金定理

哈代-拉马努金定理指出，任意自然数N的不同质因子的数量将近似等于\mathrm{\log(\log N)} 的值，对于大多数情况而言。

例如，我们将N设为1000。

15的不同质因子的数量为2和5，即2个不同的质因子。

\mathrm{\log_{e}(\log_{e}(1000))}
的值等于1.932，近似等于2。

以上情况证明了哈代-拉马努金定理。

由于该定理指出大部分情况下不同质因子的数量将近似等于\mathrm{\log(\log(N))}。但也存在定理不适用的情况。

例如，N=286

N的不同质因子的数量为2、11和13。N有3个不同的质因子。

根据哈代-拉马努金定理，N的不同质因子的数量将近似等于\mathrm{\log_{e}(\log_{e}(286))=1.732}

我们将在C++程序中实现该定理，通过计算N的不同质因子以及\mathrm{\log(\log(N))}的值，检查它们是否近似相等。

C++中实现哈代-拉马努金定理

为了检查任意自然数N的定理，我们可以通过创建一个函数来计算N的所有不同质因子，然后计算N的不同质因子的数量，并根据哈代-拉马努金定理计算N的近似不同质因子数量，即\mathrm{\log(\log(N))}的值。

可以使用C++中的log()函数计算N的不同质因子的数量，该函数返回传入的任意正整数的自然对数值。

语法

int N;
int value=log(N);

根据Hardy-Ramanujan定理，将任意数字的不同质因数的大致数量与实际的不同质因数的数量进行比较，我们将创建一个函数来计算任意数字的不同质因数的数量。

我们将检查数字N是否可被2整除，如果可以，我们将通过2除以N直到余数为0，并将不同质因数的计数加1。现在，我们将在一个for循环中迭代从i=3到i<=sqrt(N)，以检查每个奇数i的值，因为此时N将为奇数。如果N可被i整除，我们将除以i，直到余数为0，并且每次都更新N。类似地，我们将迭代和检查每个小于或等于N平方根的i值，并且在i除以N时每次迭代都将计数加1。

现在对于当N大于2且为质数时，我们将增加1来获得N的确切的不同质因数的数量。

我们将打印出计算的确切不同质因数的数量以及根据Hardy-Ramanujan定理计算的N的不同质因数的大致数量，以检查任何自然数N的定理。

在C++中实现这个方法的步骤：

• 我们将制作一个函数来获得N的确切不同质因数的数量，这将是用户输入，如上所述。

• 我们将打印出N的确切不同质因数的数量。

• 现在，我们将通过计算\mathrm{\log(\log(N))}的值来计算N的不同质因数的大致数量，并将其存储在一个变量中。

• 根据Hardy-Ramanujan定理打印出N的不同质因数的大致数量。

示例

//C++ code for the Hardy-Ramanujan theorem
#include <bits/stdc++.h>

using namespace std;

//function to count exact number of distinct prime factors of N
int exact_count(int N){

    int a=0; //to store the count of distinct prime factors

    if(N%2==0){ //if N is divisible by 2

        a++; //increase the count by 1
        while(N%2==0){ //divide N by 2 until it gives remainder as 0
            N = N/2;
        }
    }

    //N must be odd now so checking for odd values of i
    for(int i=3;i<=sqrt(N);i=i+2){
        if(N%i==0){ //if N is divisible by i
            a++; //increase the count by 1
            while(N%i==0){ //divide N by i until it gives 0 remainder
                N = N/i;
            }
        }
    }
    //for the case when N will be prime number greater than 2
    if(N>2){
        a++;
    }

    return a; //return the count of prime factors
}

int main()
{
    int N=39573; //for taking input

    double approx; //for calculating approximate no of distinct prime factors
    approx = log(log(N)); //according to Hardy-Ramanujan theorem

    //printing exact no of distinct prime factors
    cout<<"Exact no. of distinct prime factors : "<<exact_count(N)<<endl;

    cout<<"No. of distinct prime factors acc. to Hardy-Ramanujan theorem : "<<approx<<endl;

    return 0;
}

输出

Exact no. of distinct prime factors : 2
No. of distinct prime factors acc. to Hardy−Ramanujan theorem : 2.35952

时间复杂度 − O(sqrt(N)), 计算确切数量的不同素因子所需的时间。

空间复杂度 − O(1)，因为我们没有使用任何额外的空间。

结论

本文讨论了 Hardy−Ramanujan 定理及其不同方面。我们使用该定理的概念来查看任何自然数N的不同素因子数量，并检查定理的可靠性。

希望您通过阅读本文更好地理解这个主题。