Ramanujan Prime | C # 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
using System ; using System . Collections . Generic ; class GFG { static int MAX = 1000000 ; static List < int > addPrimes ( ) { int n = MAX ; 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 ] == true ) { for ( int i = p * p ; i <= n ; i += p ) prime [ i ] = false ; } } List < int > ans = new List < int > ( ) ; for ( int p = 2 ; p <= n ; p ++ ) if ( prime [ p ] ) ans . Add ( p ) ; return ans ; } static int pi ( int x , List < int > v ) { int l = 0 , r = v . Count - 1 , m , i = - 1 ; while ( l <= r ) { m = ( l + r ) / 2 ; if ( v [ m ] <= x ) { i = m ; l = m + 1 ; } else { r = m - 1 ; } } return i + 1 ; } static int Ramanujan ( int n , List < int > v ) { int upperbound = ( int ) ( 4 * n * ( Math . Log ( 4 * n ) / Math . Log ( 2 ) ) ) ; for ( int i = upperbound ; ; i -- ) { if ( pi ( i , v ) - pi ( i / 2 , v ) < n ) return 1 + i ; } } static void Ramanujan_Numbers ( int n ) { int c = 1 ; List < int > v = addPrimes ( ) ; for ( int i = 1 ; i <= n ; i ++ ) { Console . Write ( Ramanujan ( i , v ) ) ; if ( i != n ) Console . Write ( " , ▁ " ) ; } } public static void Main ( String [ ] args ) { int n = 10 ; Ramanujan_Numbers ( n ) ; } }