哈代-拉马努金定理

哈代-拉马努金定理指出，对于大多数自然数 n，其质因数的个数大约为 log(log(n))。

让我们来看几个示例：

> 5192 有 2 个不同的质因数，而 log(log(5192)) = 2.1615

> 51242183 有 3 个不同的质因数，而 log(log(51242183)) = 2.8765

正如定理所述，这只是一个近似值。当然也存在着反例，例如：

> 510510 有 7 个不同的质因数，但 log(log(510510)) = 2.5759

> 1048576 只有 1 个质因数，但 log(log(1048576)) = 2.62922

该定理主要用于近似算法，其证明也引出了概率论中更大的概念。

C++ 实现

// CPP program to count all prime factors
#include 
using namespace std;

// A function to count prime factors of
// a given number n
int exactPrimeFactorCount(int n)
{
    int count = 0;

    if (n % 2 == 0) {
        count++;
        while (n % 2 == 0)
            n = n / 2;
    }

    // n must be odd at this point. So we can skip
    // one element (Note i = i +2)
    for (int i = 3; i  2)
        count++;
    return count;
}

// driver function
int main()
{
    int n = 51242183;
    cout << "The number of distinct prime factors is/are "
         << exactPrimeFactorCount(n) << endl;
    cout << "The value of log(log(n)) is "
         << log(log(n)) << endl;
    return 0;
}

Java 实现

// Java program to count all prime factors
import java.io.*;

class GFG {
    
    // A function to count prime factors of
    // a given number n
    static int exactPrimeFactorCount(int n)
    {
        int count = 0;
    
        if (n % 2 == 0) {
            count++;
            while (n % 2 == 0)
                n = n / 2;
        }
    
        // n must be odd at this point. So we can skip
        // one element (Note i = i +2)
        for (int i = 3; i  2)
            count++;
        return count;
    }
    
    // driver function
    public static void main (String[] args) 
    {
        int n = 51242183;
        System.out.println( "The number of distinct "
                            + "prime factors is/are "
            + exactPrimeFactorCount(n));
        System.out.println( "The value of log(log(n))"
                   + " is " + Math.log(Math.log(n))) ;
    }
}

// This code is contributed by anuj_67.

Python3 实现

# Python3 program to count all 
# prime factors
import math

# A function to count 
# prime factors of
# a given number n
def exactPrimeFactorCount(n) :
    count = 0
    if (n % 2 == 0) : 
        count = count + 1
        while (n % 2 == 0) :
            n = int(n / 2) 

    # n must be odd at this
    # point. So we can skip
    # one element (Note i = i +2)
    i = 3
    
    while (i  2) :
        count = count + 1
    return count

# Driver Code
n = 51242183
print ("The number of distinct prime factors is/are {}".
       format(exactPrimeFactorCount(n), end = "
"))
print ("The value of log(log(n)) is {0:.4f}"
            .format(math.log(math.log(n))))

# This code is contributed by Manish Shaw
# (manishshaw1)

C# 实现

“`csharp

// C# program to count all prime factors

using System;

class GFG {

// A function to count prime factors of

// a given number n

static int exactPrimeFactorCount(int n)

{

int count = 0;

if (n % 2 == 0) {

count++;

while (n % 2 == 0)

n = n / 2;

}

// n must be odd at this point. So

// we can skip one element

// (Note i = i +2)

for (int i = 3; i <= Math.Sqrt(n);

i = i + 2)

{

if (n % i == 0) {

count++;

while (n % i == 0)

n = n / i;

}

}

// This condition is to handle the

// case when n is a prime number

// greater than 2

if (n > 2)

count++;

return count;

}

// Driver function

public static void Main ()

{

int n = 51242183;

Console.WriteLine( "The number of"

+ " disti