Sieve of Sundaram to print all primes smaller than n | Java program to print primes smaller than n using Sieve of Sundaram . ; Prints all prime numbers smaller ; In general Sieve of Sundaram , produces primes smaller than ( 2 * x + 2 ) for a number given number x . Since we want primes smaller than n , we reduce n to half ; This array is used to separate numbers of the form i + j + 2 ij from others where 1 <= i <= j ; Initialize all elements as not marked ; Main logic of Sundaram . Mark all numbers of the form i + j + 2 ij as true where 1 <= i <= j ; Since 2 is a prime number ; Print other primes . Remaining primes are of the form 2 * i + 1 such that marked [ i ] is false . ; Driver code
import java . util . Arrays ; class GFG { static int SieveOfSundaram ( int n ) { int nNew = ( n - 1 ) / 2 ; boolean marked [ ] = new boolean [ nNew + 1 ] ; Arrays . fill ( marked , false ) ; for ( int i = 1 ; i <= nNew ; i ++ ) for ( int j = i ; ( i + j + 2 * i * j ) <= nNew ; j ++ ) marked [ i + j + 2 * i * j ] = true ; if ( n > 2 ) System . out . print ( 2 + " ▁ " ) ; for ( int i = 1 ; i <= nNew ; i ++ ) if ( marked [ i ] == false ) System . out . print ( 2 * i + 1 + " ▁ " ) ; return - 1 ; } public static void main ( String [ ] args ) { int n = 20 ; SieveOfSundaram ( n ) ; } }