# Hardy-Ramanujan Theorem

Hardy Ramanujam theorem states that the number of prime factors of n will approximately be log(log(n)) for most natural numbers n

Examples :

5192 has 2 distinct prime factors and log(log(5192)) = 2.1615
51242183 has 3 distinct prime facts and log(log(51242183)) = 2.8765

As the statement quotes, it is only an approximation. There are counter examples such as

510510 has 7 distinct prime factors but log(log(510510)) = 2.5759
1048576 has 1 prime factor but log(log(1048576)) = 2.62922

This theorem is mainly used in approximation algorithms and its proof lead to bigger concepts in probability theory.

## 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 <= ``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 ` `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 <= 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 (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 <``=` `int``(math.sqrt(n))) :  ` `        ``if` `(n ``%` `i ``=``=` `0``) :      ` `            ``count ``=` `count ``+` `1` `            ``while` `(n ``%` `i ``=``=` `0``) : ` `                ``n ``=` `int``(n ``/` `i) ` `        ``i ``=` `i ``+` `2` ` `  `    ``# This condition is to  ` `    ``# handle the case when n ` `    ``# is a prime number greater  ` `    ``# than 2 ` `    ``if` `(n > ``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#

 `// 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"` `        ``+ ``" distinct prime factors is/are "` `              ``+ exactPrimeFactorCount(n)); ` `               `  `        ``Console.WriteLine( ``"The value of "` `                       ``+ ``"log(log(n)) is "` `                ``+ Math.Log(Math.Log(n))) ; ` `    ``} ` `} ` ` `  `// This code is contributed by anuj_67. `

## PHP

 ` 2) ` `        ``\$count``++; ` `    ``return` `\$count``; ` `} ` ` `  `    ``// Driver Code ` `    ``\$n` `= 51242183; ` `    ``echo` `"The number of distinct prime"``. ` `         ``" factors is/are "``,exactPrimeFactorCount(``\$n``),````" "````; ` `          `  `    ``echo` `"The value of log(log(n)) "``. ` `         ``"is "``,log(log(``\$n``)),````" "````; ` ` `  `// This code is contributed by m_kit ` `?> `

Output:

```The number of distinct prime factors is/are 3
The value of log(log(n)) is 2.8765
```