Data Modelling & AI Data Structure & Algorithm

Rosser’s Theorem

30 July 2024

2

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

Run Local AWS Cloud Stack using LocalStack on Linux

Learn Terraform Automation in 3 days using Video Courses

How To Expose Ansible AWX Service using Nginx Ingress

LEAVE A REPLY Cancel reply

Most Popular

How to Protect Against Walmart Gift Card Scams in 2025 by Manual Thomas

Interview With Dan Chernov – CEO of DerScanner by Shauli Zacks

5 Best Free Antiviruses for Linux in 2025: Expert Ranked by Sam Boyd

5 Best Free Online Virus Scanners & Removers for 2025 by Kate Davidson

Recent Comments

EDITOR PICKS

How to Protect Against Walmart Gift Card Scams in 2025 by Manual Thomas

Interview With Dan Chernov – CEO of DerScanner by Shauli Zacks

5 Best Free Antiviruses for Linux in 2025: Expert Ranked by Sam Boyd

POPULAR POSTS

How to Protect Against Walmart Gift Card Scams in 2025 by Manual Thomas

Interview With Dan Chernov – CEO of DerScanner by Shauli Zacks

5 Best Free Antiviruses for Linux in 2025: Expert Ranked by Sam Boyd

POPULAR CATEGORY

ABOUT US

FOLLOW US