Ramanujan Prime | CPP program to find Ramanujan numbers ; FUnction to return a vector of primes ; 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 . ; If prime [ p ] is not changed , then it is a prime ; 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 . ; Print all prime numbers ; Function to find number of primes less than or equal to x ; Binary search to find out number of primes less than or equal to x ; Function to find the nth ramanujan prime ; For n >= 1 , a ( n ) < 4 * n * log ( 4 n ) ; We start from upperbound and find where pi ( i ) - pi ( i / 2 ) < n the previous number being the nth ramanujan prime ; Function to find first n Ramanujan numbers ; Get the prime numbers ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1000000 NEW_LINE vector < int > addPrimes ( ) { int n = MAX ; bool prime [ n + 1 ] ; memset ( prime , true , sizeof ( prime ) ) ; for ( int p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= n ; i += p ) prime [ i ] = false ; } } vector < int > ans ; for ( int p = 2 ; p <= n ; p ++ ) if ( prime [ p ] ) ans . push_back ( p ) ; return ans ; } int pi ( int x , vector < int > v ) { int l = 0 , r = v . size ( ) - 1 , m , in = -1 ; while ( l <= r ) { m = ( l + r ) / 2 ; if ( v [ m ] <= x ) { in = m ; l = m + 1 ; } else { r = m - 1 ; } } return in + 1 ; } int Ramanujan ( int n , vector < int > v ) { int upperbound = 4 * n * ( log ( 4 * n ) / log ( 2 ) ) ; for ( int i = upperbound ; ; i -- ) { if ( pi ( i , v ) - pi ( i / 2 , v ) < n ) return 1 + i ; } } void Ramanujan_Numbers ( int n ) { int c = 1 ; vector < int > v = addPrimes ( ) ; for ( int i = 1 ; i <= n ; i ++ ) { cout << Ramanujan ( i , v ) ; if ( i != n ) cout << " , ▁ " ; } } int main ( ) { int n = 10 ; Ramanujan_Numbers ( n ) ; return 0 ; }