Sieve of Sundaram to print all primes smaller than n | 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 ; 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
< ? php function SieveOfSundaram ( $ n ) { $ nNew = ( $ n - 1 ) / 2 ; $ marked = array_fill ( 0 , ( $ nNew + 1 ) , false ) ; for ( $ i = 1 ; $ i <= $ nNew ; $ i ++ ) for ( $ j = $ i ; ( $ i + $ j + 2 * $ i * $ j ) <= $ nNew ; $ j ++ ) $ marked [ $ i + $ j + 2 * $ i * $ j ] = true ; if ( $ n > 2 ) echo "2 ▁ " ; for ( $ i = 1 ; $ i <= $ nNew ; $ i ++ ) if ( $ marked [ $ i ] == false ) echo ( 2 * $ i + 1 ) . " ▁ " ; } $ n = 20 ; SieveOfSundaram ( $ n ) ; ? >