Ramanujan Prime
The Nth Ramanujan prime is the least integer Rn for which
where ?(x) is a prime-counting function
Note that the integer Rn is necessarily a prime number: ?(x) – ?(x/2) and, hence, ?(x) must increase by obtaining another prime at x = Rn. Since ?(x) – ?(x/2) can increase by at most 1,
Range of Rn is (2n log(2n), 4n log(4n)).
Ramanujan primes:
2, 11, 17, 29, 41, 47, 59, 67, 71, 97
For a given N, the task is to print first N Ramanujan primes
Examples:
Input : N = 5
Output : 2, 11, 17, 29, 41
Input : N = 10
Output : 2, 11, 17, 29, 41, 47, 59, 67, 71, 97
Approach:
Let us divide our solution into parts,
First, we will use sieve of Eratosthenes to get all the primes less than 10^6
Now we will have to find the value of ?(x), ?(x) is the count of primes which are less than or equal to x. Primes are stored in increasing order. So we can perform a binary search to find all the primes less than x, which can be done in O(log n).
Now we have the range Rn lies between : 2n log(2n) < Rn < 4n log(4n) So, we will take the upper bound and iterate from upper bound to the lower bound until ?(i) – ?(i/2) < n, i+1 is the nth Ramanujan prime.
Below is the implementation of the above approach :
C++
// CPP program to find Ramanujan numbers #include <bits/stdc++.h> using namespace std; #define MAX 1000000 // FUnction to return a vector of primes vector< int > addPrimes() { int n = MAX; // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. bool prime[n + 1]; memset (prime, true , sizeof (prime)); for ( int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true ) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ( int i = p * p; i <= n; i += p) prime[i] = false ; } } vector< int > ans; // Print all prime numbers for ( int p = 2; p <= n; p++) if (prime[p]) ans.push_back(p); return ans; } // Function to find number of primes // less than or equal to x int pi( int x, vector< int > v) { int l = 0, r = v.size() - 1, m, in = -1; // Binary search to find out number of // primes less than or equal to x while (l <= r) { m = (l + r) / 2; if (v[m] <= x) { in = m; l = m + 1; } else { r = m - 1; } } return in + 1; } // Function to find the nth ramanujan prime int Ramanujan( int n, vector< int > v) { // For n>=1, a(n)<4*n*log(4n) int upperbound = 4 * n * ( log (4 * n) / log (2)); // We start from upperbound and find where // pi(i)-pi(i/2)<n the previous number being // the nth ramanujan prime for ( int i = upperbound;; i--) { if (pi(i, v) - pi(i / 2, v) < n) return 1 + i; } } // Function to find first n Ramanujan numbers void Ramanujan_Numbers( int n) { int c = 1; // Get the prime numbers vector< int > v = addPrimes(); for ( int i = 1; i <= n; i++) { cout << Ramanujan(i, v); if (i!=n) cout << ", " ; } } // Driver code int main() { int n = 10; Ramanujan_Numbers(n); return 0; } |
Java
// Java program to find Ramanujan numbers import java.util.*; class GFG { static int MAX = 1000000 ; // FUnction to return a vector of primes static Vector<Integer> addPrimes() { int n = MAX; // Create a boolean array "prime[0..n]" and // initialize all entries it as true. // A value in prime[i] will finally be false // if i is Not a prime, else true. boolean []prime= new boolean [n + 1 ]; Arrays.fill(prime, true ); for ( int p = 2 ; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true ) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ( int i = p * p; i <= n; i += p) prime[i] = false ; } } Vector<Integer> ans = new Vector<Integer>(); // Print all prime numbers for ( int p = 2 ; p <= n; p++) if (prime[p]) ans.add(p); return ans; } // Function to find number of primes // less than or equal to x static int pi( int x, Vector<Integer> v) { int l = 0 , r = v.size() - 1 , m, in = - 1 ; // Binary search to find out number of // primes less than or equal to x while (l <= r) { m = (l + r) / 2 ; if (v.get(m) <= x) { in = m; l = m + 1 ; } else { r = m - 1 ; } } return in + 1 ; } // Function to find the nth ramanujan prime static int Ramanujan( int n, Vector<Integer> v) { // For n>=1, a(n)<4*n*log(4n) int upperbound = ( int ) ( 4 * n * (Math.log( 4 * n) / Math.log( 2 ))); // We start from upperbound and find where // pi(i)-pi(i/2)<n the previous number being // the nth ramanujan prime for ( int i = upperbound;; i--) { if (pi(i, v) - pi(i / 2 , v) < n) return 1 + i; } } // Function to find first n Ramanujan numbers static void Ramanujan_Numbers( int n) { int c = 1 ; // Get the prime numbers Vector<Integer> v = addPrimes(); for ( int i = 1 ; i <= n; i++) { System.out.print(Ramanujan(i, v)); if (i != n) System.out.print( ", " ); } } // Driver code public static void main(String[] args) { int n = 10 ; Ramanujan_Numbers(n); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find Ramanujan numbers from math import log, ceil MAX = 1000000 # FUnction to return a vector of primes def addPrimes(): n = MAX # Create a boolean array "prime[0..n]" # and initialize all entries it as true. # A value in prime[i] will finally be # false if i is Not a prime, else true. prime = [ True for i in range (n + 1 )] for p in range ( 2 , n + 1 ): if p * p > n: break # If prime[p] is not changed, # then it is a prime if (prime[p] = = True ): # Update all multiples of p # greater than or equal to the # square of it. numbers which are # multiple of p and are less than p^2 # are already been marked. for i in range ( 2 * p, n + 1 , p): prime[i] = False ans = [] # Print all prime numbers for p in range ( 2 , n + 1 ): if (prime[p]): ans.append(p) return ans # Function to find number of primes # less than or equal to x def pi(x, v): l, r = 0 , len (v) - 1 # Binary search to find out number of # primes less than or equal to x m, i = 0 , - 1 while (l < = r): m = (l + r) / / 2 if (v[m] < = x): i = m l = m + 1 else : r = m - 1 return i + 1 # Function to find the nth ramanujan prime def Ramanujan(n, v): # For n>=1, a(n)<4*n*log(4n) upperbound = ceil( 4 * n * (log( 4 * n) / log( 2 ))) # We start from upperbound and find where # pi(i)-pi(i/2)<n the previous number being # the nth ramanujan prime for i in range (upperbound, - 1 , - 1 ): if (pi(i, v) - pi(i / 2 , v) < n): return 1 + i # Function to find first n Ramanujan numbers def Ramanujan_Numbers(n): c = 1 # Get the prime numbers v = addPrimes() for i in range ( 1 , n + 1 ): print (Ramanujan(i, v), end = "") if (i ! = n): print (end = ", " ) # Driver code n = 10 Ramanujan_Numbers(n) # This code is contributed # by Mohit Kumar |
C#
// C# program to find Ramanujan numbers using System; using System.Collections.Generic; class GFG { static int MAX = 1000000; // FUnction to return a vector of primes static List< int > addPrimes() { int n = MAX; // Create a boolean array "prime[0..n]" and // initialize all entries it as true. // A value in prime[i] will finally be false // if i is Not a prime, else true. Boolean []prime = new Boolean[n + 1]; for ( int i = 0; i < n + 1; i++) prime[i] = true ; for ( int p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true ) { // Update all multiples of p greater than // or equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ( int i = p * p; i <= n; i += p) prime[i] = false ; } } List< int > ans = new List< int >(); // Print all prime numbers for ( int p = 2; p <= n; p++) if (prime[p]) ans.Add(p); return ans; } // Function to find number of primes // less than or equal to x static int pi( int x, List< int > v) { int l = 0, r = v.Count - 1, m, i = -1; // Binary search to find out number of // primes less than or equal to x while (l <= r) { m = (l + r) / 2; if (v[m] <= x) { i = m; l = m + 1; } else { r = m - 1; } } return i + 1; } // Function to find the nth ramanujan prime static int Ramanujan( int n, List< int > v) { // For n>=1, a(n)<4*n*log(4n) int upperbound = ( int ) (4 * n * (Math.Log(4 * n) / Math.Log(2))); // We start from upperbound and find where // pi(i)-pi(i/2)<n the previous number being // the nth ramanujan prime for ( int i = upperbound;; i--) { if (pi(i, v) - pi(i / 2, v) < n) return 1 + i; } } // Function to find first n Ramanujan numbers static void Ramanujan_Numbers( int n) { int c = 1; // Get the prime numbers List< int > v = addPrimes(); for ( int i = 1; i <= n; i++) { Console.Write(Ramanujan(i, v)); if (i != n) Console.Write( ", " ); } } // Driver code public static void Main(String[] args) { int n = 10; Ramanujan_Numbers(n); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find Ramanujan numbers const MAX = 1000000; // FUnction to return a vector of primes function addPrimes() { let n = MAX; // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. let prime = new Array(n + 1).fill( true ); for (let p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true ) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (let i = p * p; i <= n; i += p) prime[i] = false ; } } let ans = []; // Print all prime numbers for (let p = 2; p <= n; p++) if (prime[p]) ans.push(p); return ans; } // Function to find number of primes // less than or equal to x function pi(x, v) { let l = 0, r = v.length - 1, m, inn = -1; // Binary search to find out number of // primes less than or equal to x while (l <= r) { m = parseInt((l + r) / 2); if (v[m] <= x) { inn = m; l = m + 1; } else { r = m - 1; } } return inn + 1; } // Function to find the nth ramanujan prime function Ramanujan(n, v) { // For n>=1, a(n)<4*n*log(4n) let upperbound = 4 * n * parseInt((Math.log(4 * n) / Math.log(2))); // We start from upperbound and find where // pi(i)-pi(i/2)<n the previous number being // the nth ramanujan prime for (let i = upperbound;; i--) { if (pi(i, v) - pi(parseInt(i / 2), v) < n) return 1 + i; } } // Function to find first n Ramanujan numbers function Ramanujan_Numbers(n) { let c = 1; // Get the prime numbers let v = addPrimes(); for (let i = 1; i <= n; i++) { document.write(Ramanujan(i, v)); if (i!=n) document.write( ", " ); } } // Driver code let n = 10; Ramanujan_Numbers(n); </script> |
Output:
2, 11, 17, 29, 41, 47, 59, 67, 71, 97
Time Complexity : O(nlogn)
Auxiliary Space: O(MAX)