Ramanujan Prime | Python3 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
from math import log , ceil NEW_LINE MAX = 1000000 NEW_LINE def addPrimes ( ) : NEW_LINE INDENT n = MAX NEW_LINE prime = [ True for i in range ( n + 1 ) ] NEW_LINE for p in range ( 2 , n + 1 ) : NEW_LINE INDENT if p * p > n : NEW_LINE INDENT break NEW_LINE DEDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( 2 * p , n + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT DEDENT ans = [ ] NEW_LINE for p in range ( 2 , n + 1 ) : NEW_LINE INDENT if ( prime [ p ] ) : NEW_LINE INDENT ans . append ( p ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def pi ( x , v ) : NEW_LINE INDENT l , r = 0 , len ( v ) - 1 NEW_LINE m , i = 0 , - 1 NEW_LINE while ( l <= r ) : NEW_LINE INDENT m = ( l + r ) // 2 NEW_LINE if ( v [ m ] <= x ) : NEW_LINE INDENT i = m NEW_LINE l = m + 1 NEW_LINE DEDENT else : NEW_LINE INDENT r = m - 1 NEW_LINE DEDENT DEDENT return i + 1 NEW_LINE DEDENT def Ramanujan ( n , v ) : NEW_LINE INDENT upperbound = ceil ( 4 * n * ( log ( 4 * n ) / log ( 2 ) ) ) NEW_LINE for i in range ( upperbound , - 1 , - 1 ) : NEW_LINE INDENT if ( pi ( i , v ) - pi ( i / 2 , v ) < n ) : NEW_LINE INDENT return 1 + i NEW_LINE DEDENT DEDENT DEDENT def Ramanujan_Numbers ( n ) : NEW_LINE INDENT c = 1 NEW_LINE v = addPrimes ( ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT print ( Ramanujan ( i , v ) , end = " " ) NEW_LINE if ( i != n ) : NEW_LINE INDENT print ( end = " , ▁ " ) NEW_LINE DEDENT DEDENT DEDENT n = 10 NEW_LINE Ramanujan_Numbers ( n ) NEW_LINE