Rosser’s Theorem

In mathematics, Rosser’s Theorem states that the nth prime number is greater than the product of n and natural logarithm of n for all n greater than 1.
Mathematically,
For n >= 1, if p_n is the nth prime number, then
p_n > n * (ln n)

Illustrative Examples:
      
       For n = 1, nth prime number = 2
    2 > 1 * ln(1)
Explanations, the above relation inherently holds true and it verifies the 
statement of Rosser's Theorem clearly.
Some more examples are, 
       For n = 2, nth prime number = 3
    3 > 2 * ln(2)
       For n = 3, nth prime number = 5
    5 > 3 * ln(3)
       For n = 4, nth prime number = 7
    7 > 4 * ln(4)
       For n = 5, nth prime number = 11
    11 > 5 * ln(5)
       For n = 6, nth prime number = 13
    13 > 6 * ln(6)

Approach for code:
Efficient generation of prime numbers using prime sieve and checking the condition of Rosser’s Theorem for each prime number individually.

C++

// CPP code to verify Rosser's Theorem
#include <bits/stdc++.h>
using namespace std;
 
#define show(x) cout << #x << " = " << x << "\n";
 
vector<int> prime;
 
// Sieve of Eratosthenes
void sieve()
{
    // prime sieve to generate prime numbers efficiently
    int n = 1e5;
    vector<bool> isprime(n + 2, true);
    isprime[0] = isprime[1] = false;
    for (long long i = 2; i <= n; i++) {
        if (isprime[i]) {
            for (long long j = i * i; j <= n; j += i)
                isprime[j] = false;
        }
    }
    // store primes in prime[] vector
    for (int i = 0; i <= n; i++)
        if (isprime[i])
            prime.push_back(i);
}
 
// Verifies ROSSER'S THEOREM for all numbers 
// smaller than n.
void verifyRosser(int n)
{
    cout << "ROSSER'S THEOREM: nth prime "
            "number > n * (ln n)\n";
    for (int i = 0; i < n; i++)
        if (prime[i] > (i + 1) * log(i + 1)) {
            cout << "For n = " << i + 1
                 << ", nth prime number = "
                 << prime[i] << "\n\t"
                 << prime[i] << " > " << i + 1 
                 << " * ln(" << i + 1 << ")\n";
        }
}
 
 
int main()
{
    sieve();
    verifyRosser(20);
    return 0;
}

Java

// Java code to verify Rosser's Theorem
 
import java.util.*;
class GFG
{
    static Vector<Integer> prime=new Vector<Integer>(); 
    // Sieve of Eratosthenes
    static void sieve()
    {
        // prime sieve to generate prime numbers efficiently
        int n = 10000;
        boolean []isprime=new boolean[n+2];
        for(int i=0;i<n;i++)
        isprime[i]=true;
         
        isprime[0]=false;
        isprime[1] =false;
        for (int i = 2; i <= n; i++) {
            if (isprime[i]) {
                for (int j = i * i; j <= n; j += i)
                    isprime[j] =false;
            }
        }
        // store primes in prime[] vector
        for (int i = 0; i <= n; i++)
            if (isprime[i])
                prime.add(i);
    }
     
    // Verifies ROSSER'S THEOREM for all numbers 
    // smaller than n.
    static void verifyRosser(int n)
    {
        System.out.println("ROSSER'S THEOREM: nth prime number > n * (ln n)");
                 
        for (int i = 0; i < n; i++)
            if (prime.get(i) > (i + 1) * Math.log(i + 1)) {
                System.out.println( "For n = " + (i+1) 
                    + ", nth prime number = "
                    + prime.get(i) + "\n\t"
                    + prime.get(i) + " > " + (i + 1)
                    + " * ln(" + (i + 1) + ")");
            }
    }
     
    // Driver code
    public static void main(String [] args)
    {
        sieve();
        verifyRosser(20);
         
    }
}
 
// This code is contributed by ihritik

Python3

# Python3 code to verify Rosser's Theorem
import math
prime = [];
 
# Sieve of Eratosthenes
def sieve():
     
    # prime sieve to generate 
    # prime numbers efficiently
    n = 100001;
    isprime = [True] * (n + 2);
    isprime[0] = False;
    isprime[1] = False;
    for i in range(2, n + 1):
        if(isprime[i]):
            j = i * i;
            while (j <= n):
                isprime[j] = False;
                j += i;
     
    # store primes in 
    # prime[] vector
    for i in range(n + 1):
        if (isprime[i]):
            prime.append(i);
 
# Verifies ROSSER'S THEOREM 
# for all numbers smaller than n.
def verifyRosser(n):
     
    print("ROSSER'S THEOREM: nth", 
          "prime number > n * (ln n)");
    for i in range(n):
        if (prime[i] > int((i + 1) * math.log(i + 1))):
            print("For n =", (i + 1), ", nth prime number =", 
                   prime[i], "\n\t", prime[i], " >", (i + 1), 
                                      "* ln(", (i + 1), ")");
 
# Driver Code
sieve();
verifyRosser(20);
 
# This code is contributed 
# by mits

C#

// C# code to verify Rosser's Theorem
using System;
using System.Collections.Generic;
     
class GFG
{
    static List<int> prime = new List<int>(); 
     
    // Sieve of Eratosthenes
    static void sieve()
    {
        // prime sieve to generate 
        // prime numbers efficiently
        int n = 10000;
        bool []isprime = new bool[n + 2];
        for(int i = 0; i < n; i++)
        isprime[i] = true;
         
        isprime[0] = false;
        isprime[1] = false;
        for (int i = 2; i <= n; i++) 
        {
            if (isprime[i])
            {
                for (int j = i * i; 
                         j <= n; j += i)
                    isprime[j] = false;
            }
        }
         
        // store primes in prime[] vector
        for (int i = 0; i <= n; i++)
            if (isprime[i])
                prime.Add(i);
    }
     
    // Verifies ROSSER'S THEOREM for 
    // all numbers smaller than n.
    static void verifyRosser(int n)
    {
        Console.WriteLine("ROSSER'S THEOREM: " +    
                          "nth prime number > n * (ln n)");
                 
        for (int i = 0; i < n; i++)
            if (prime[i] > (i + 1) * Math.Log(i + 1)) 
            {
                Console.WriteLine( "For n = " + (i + 1) + 
                                ", nth prime number = " + 
                           prime[i] + "\n\t" + prime[i] + 
                             " > " + (i + 1) + " * ln(" + 
                                          (i + 1) + ")");
            }
    }
     
    // Driver code
    public static void Main(String [] args)
    {
        sieve();
        verifyRosser(20);
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// JavaScript code to verify
// Rosser's Theorem
let prime = new Array();
let y = 0;
 
// function show(x)
// {echo x" = ".x."\n";}
 
// Sieve of Eratosthenes
function sieve()
{
    // prime sieve to generate
    // prime numbers efficiently
    let n = 100001;
    let isprime = new Array(n + 2).fill(true);
    isprime[0] = false;
    isprime[1] = false;
    for (let i = 2; i <= n; i++)
    {
        if (isprime[i])
        {
            for (let j = i * i;
                j <= n; j += i)
                isprime[j] = false;
        }
    }
     
    // store primes in
    // prime[] vector
    for (let i = 0; i <= n; i++)
        if (isprime[i])
            prime[y++] = i;
}
 
// Verifies ROSSER'S THEOREM
// for all numbers smaller than n.
function verifyRosser(n)
{    
    document.write(
    "ROSSER'S THEOREM: nth prime number > n * (ln n) <br>"
    );
    for (let i = 0; i < n; i++)
        if (prime[i] > Math.floor((i + 1) * Math.log(i + 1)))
        {
            document.write("For n = " + (i + 1) +
                ", nth prime number = " +
                prime[i] + "<br>" +
                prime[i] + " > " +
                (i + 1) + " * ln(" +
                (i + 1) + ")<br>");
        }
}
 
// Driver Code
sieve();
verifyRosser(20);
 
// This code is contributed by gfgking
 
</script>

PHP

<?php
// PHP code to verify 
// Rosser's Theorem
$prime;
$y = 0;
 
// function show($x)
// {echo $x" = ".$x."\n";}
 
// Sieve of Eratosthenes
function sieve()
{
    global $prime,$y;
     
    // prime sieve to generate 
    // prime numbers efficiently
    $n = 100001;
    $isprime = array_fill(0, ($n + 2), true);
    $isprime[0] = false;
    $isprime[1] = false;
    for ($i = 2; $i <= $n; $i++)
    {
        if ($isprime[$i]) 
        {
            for ($j = $i * $i; 
                 $j <= $n; $j += $i)
                $isprime[$j] = false;
        }
    }
     
    // store primes in 
    // prime[] vector
    for ($i = 0; $i <= $n; $i++)
        if ($isprime[$i])
            $prime[$y++]=$i;
}
 
// Verifies ROSSER'S THEOREM 
// for all numbers smaller than n.
function verifyRosser($n)
{
    global $prime;
     
    echo "ROSSER'S THEOREM: nth " . 
         "prime number > n * (ln n)\n";
    for ($i = 0; $i < $n; $i++)
        if ($prime[$i] > (int)(($i + 1) * log($i + 1)))
        {
            echo "For n = " . ($i + 1).
                 ", nth prime number = " . 
                  $prime[$i] . "\n\t" . 
                  $prime[$i] . " > " . 
                  ($i + 1) . " * ln(" . 
                  ($i + 1) . ")\n";
        }
}
 
// Driver Code
sieve();
verifyRosser(20);
 
// This code is contributed 
// by mits
?>

Output

ROSSER'S THEOREM: nth prime number > n * (ln n)
For n = 1, nth prime number = 2
    2 > 1 * ln(1)
For n = 2, nth prime number = 3
    3 > 2 * ln(2)
For n = 3, nth prime number = 5
    5 > 3 * ln(3)
For n = 4, nth prime number = 7
    7 > 4 * ln(4)
For n = 5, nth prime number = 11
    11 > 5 * ln(5)
For n = 6, nth prime number = 13
    13 > 6 * ln(6)
For n = 7, nth prime number = 17
    17 > 7 * ln(7)
For n = 8, nth prime number = 19
    19 > 8 * ln(8)
For n = 9, nth prime number = 23
    23 > 9 * ln(9)
For n = 10, nth prime number = 29
    29 > 10 * ln(10)
For n = 11, nth prime number = 31
    31 > 11 * ln(11)
For n = 12, nth prime number = 37
    37 > 12 * ln(12)
For n = 13, nth prime number = 41
    41 > 13 * ln(13)
For n = 14, nth prime number = 43
    43 > 14 * ln(14)
For n = 15, nth prime number = 47
    47 > 15 * ln(15)
For n = 16, nth prime number = 53
    53 > 16 * ln(16)
For n = 17, nth prime number = 59
    59 > 17 * ln(17)
For n = 18, nth prime number = 61
    61 > 18 * ln(18)
For n = 19, nth prime number = 67
    67 > 19 * ln(19)
For n = 20, nth prime number = 71
    71 > 20 * ln(20)

Time Complexity: O(n*log(log(n)))
Auxiliary Space: O(n)

Another Approach :

C++

#include <bits/stdc++.h>
using namespace std;
 
#define show(x) cout << #x << " = " << x << "\n";
 
// Computes the nth prime number using the sieve of Eratosthenes
int nthPrime(int n)
{
    int maxN = max((int)(1.2 * n * log(n)), 20); // maxN is an estimate of the nth prime
    vector<bool> isprime(maxN + 1, true);
    int count = 0;
    for (int i = 2; i <= maxN; i++) {
        if (isprime[i]) {
            count++;
            if (count == n) {
                return i;
            }
            for (int j = i * i; j <= maxN; j += i) {
                isprime[j] = false;
            }
        }
    }
    return -1; // nth prime not found
}
 
// Verifies ROSSER'S THEOREM for all numbers 
// smaller than n.
void verifyRosser(int n)
{
    cout << "ROSSER'S THEOREM: nth prime "
            "number > n * (ln n)\n";
    for (int i = 1; i <= n; i++) {
        int nth = nthPrime(i);
        if (nth > i * log(i)) {
            cout << "For n = " << i << ", nth prime number = "
                 << nth << "\n\t"
                 << nth << " > " << i << " * ln(" << i << ")\n";
        }
    }
}
 
int main()
{
    verifyRosser(20);
    return 0;
}

Java

import java.util.Arrays;
 
public class GFG {
 
    // Computes the nth prime number using the sieve of Eratosthenes
    static int nthPrime(int n) {
        int maxN = Math.max((int) (1.2 * n * Math.log(n)), 20); // maxN is an estimate of the nth prime
        boolean[] isPrime = new boolean[maxN + 1];
        Arrays.fill(isPrime, true);
 
        int count = 0;
        for (int i = 2; i <= maxN; i++) {
            if (isPrime[i]) {
                count++;
                if (count == n) {
                    return i;
                }
                for (int j = i * i; j <= maxN; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        return -1; // nth prime not found
    }
 
    // Verifies ROSSER'S THEOREM for all numbers 
    // smaller than n.
    static void verifyRosser(int n) {
        System.out.println("ROSSER'S THEOREM: nth prime number > n * (ln n)");
        for (int i = 1; i <= n; i++) {
            int nth = nthPrime(i);
            if (nth > i * Math.log(i)) {
                System.out.println("For n = " + i + ", nth prime number = " + nth);
                System.out.println("\t" + nth + " > " + i + " * ln(" + i + ")");
            }
        }
    }
 
    public static void main(String[] args) {
        verifyRosser(20);
    }
}

Python3

import math
 
# Computes the nth prime number using the sieve of Eratosthenes
def nth_prime(n):
    maxN = max(int(1.2 * n * math.log(n)), 20)  # maxN is an estimate of the nth prime
    isprime = [True] * (maxN + 1)
    count = 0
    for i in range(2, maxN + 1):
        if isprime[i]:
            count += 1
            if count == n:
                return i
            for j in range(i * i, maxN + 1, i):
                isprime[j] = False
    return -1  # nth prime not found
 
# Verifies ROSSER'S THEOREM for all numbers smaller than n.
def verify_rosser(n):
    print("ROSSER'S THEOREM: nth prime number > n * ln n")
    for i in range(1, n + 1):
        nth = nth_prime(i)
        if nth > i * math.log(i):
            print(f"For n = {i}, nth prime number = {nth}")
            print(f"{nth} > {i} * ln({i})")
 
if __name__ == "__main__":
    verify_rosser(20)

C#

using System;
using System.Collections.Generic;
 
namespace RosserTheoremVerification
{
    class GFG
    {
        // Computes the nth prime number using the sieve of Eratosthenes
        static int NthPrime(int n)
        {
            int maxN = (int)(1.2 * n * Math.Log(n)); // maxN is an estimate of the nth prime
            List<bool> isprime = new List<bool>(new bool[maxN + 1]);
            int count = 0;
            for (int i = 2; i <= maxN; i++)
            {
                if (isprime[i])
                {
                    count++;
                    if (count == n)
                    {
                        return i;
                    }
                    for (int j = i * i; j <= maxN; j += i)
                    {
                        isprime[j] = false;
                    }
                }
            }
            return -1; // nth prime not found
        }
 
        // Verifies ROSSER'S THEOREM for all numbers 
        // smaller than n.
        static void VerifyRosser(int n)
        {
            Console.WriteLine("ROSSER'S THEOREM: nth prime number > n * (ln n)");
            for (int i = 1; i <= n; i++)
            {
                int nth = NthPrime(i);
                if (nth > i * Math.Log(i))
                {
                    Console.WriteLine($"For n = {i}, nth prime number = {nth}");
                    Console.WriteLine($"\t{nth} > {i} * ln({i})");
                }
            }
        }
 
        static void Main(string[] args)
        {
            VerifyRosser(20);
        }
    }
}

Javascript

// Computes the nth prime number using the sieve of Eratosthenes
function nthPrime(n)
{
    let maxN = Math.max(Math.floor((1.2 * n * Math.log(n))), 20); // maxN is an estimate of the nth prime
    let isprime=new Array(maxN + 1).fill(true);
    let count = 0;
    for (let i = 2; i <= maxN; i++) {
        if (isprime[i]) {
            count++;
            if (count == n) {
                return i;
            }
            for (let j = i * i; j <= maxN; j += i) {
                isprime[j] = false;
            }
        }
    }
    return -1; // nth prime not found
}
 
// Verifies ROSSER'S THEOREM for all numbers 
// smaller than n.
function verifyRosser( n)
{
    document.write("ROSSER'S THEOREM: nth prime " +
            "number > n * (ln n)");
    for (let i = 1; i <= n; i++) {
        let nth = nthPrime(i);
        if (nth > i * Math.floor(Math.log(i))) {
            document.write("For n = " + i + ", nth prime number = "
                 + nth + "\n\t"
                 + nth + " > " + i + " * ln(" + i + ")");
        }
    }
}
    
verifyRosser(20);

Output :

ROSSER'S THEOREM : nth prime number >n *(ln n) 
for n = 1, nth prime number = 2
    2 > 1 * ln(1)
For n = 2, nth prime number = 3
    3 > 2 * ln(2)
For n = 3, nth prime number = 5
    5 > 3 * ln(3)
For n = 4, nth prime number = 7
    7 > 4 * ln(4)
For n = 5, nth prime number = 11
    11 > 5 * ln(5)
For n = 6, nth prime number = 13
    13 > 6 * ln(6)
For n = 7, nth prime number = 17
    17 > 7 * ln(7)
For n = 8, nth prime number = 19
    19 > 8 * ln(8)
For n = 9, nth prime number = 23
    23 > 9 * ln(9)
For n = 10, nth prime number = 29
    29 > 10 * ln(10)
For n = 11, nth prime number = 31
    31 > 11 * ln(11)
For n = 12, nth prime number = 37
    37 > 12 * ln(12)
For n = 13, nth prime number = 41
    41 > 13 * ln(13)
For n = 14, nth prime number = 43
    43 > 14 * ln(14)
For n = 15, nth prime number = 47
    47 > 15 * ln(15)
For n = 16, nth prime number = 53
    53 > 16 * ln(16)
For n = 17, nth prime number = 59
    59 > 17 * ln(17)
For n = 18, nth prime number = 61
    61 > 18 * ln(18)
For n = 19, nth prime number = 67
    67 > 19 * ln(19)
For n = 20, nth prime number = 71
    71 > 20 * ln(20)

Time Complexity: O(n*log(log(n)))
Auxiliary Space: O(n)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Rosser’s Theorem

C++

Java

Python3

C#

Javascript

PHP

C++

Java

Python3

C#

Javascript

Algorithms Quiz | Sudo Placement [1.8] | Question 15

Create new Mobile Number by selecting maximum from ends after inserting pairwise absolute difference in middle

Php Program To Check If A String Is Substring Of Another

LEAVE A REPLY Cancel reply

Most Popular

7 Best Books for Learning SQL [2024 Edition]

Introduction to Web Scraping

Must Do Coding Questions for Product Based Companies

Algorithm to solve Rubik’s Cube

Recent Comments

EDITOR PICKS

Weak References in Python

D3.js geoHammerRetroazimuthal() Function

Partition string into two substrings having maximum number of common non-repeating characters

POPULAR POSTS

React.js Blueprint Card Component Props

JavaScript Number() Constructor

Fabric.js Circle flipY Property

POPULAR CATEGORY

ABOUT US

FOLLOW US