Sieve of Atkin | PHP program for implementation of Sieve of Atkin ; 2 and 3 are known to be prime ; Initialise the sieve array with false values ; Mark sieve [ n ] is true if one of the following is true : a ) n = ( 4 * x * x ) + ( y * y ) has odd number of solutions , i . e . , there exist odd number of distinct pairs ( x , y ) that satisfy the equation and n % 12 = 1 or n % 12 = 5. b ) n = ( 3 * x * x ) + ( y * y ) has odd number of solutions and n % 12 = 7 c ) n = ( 3 * x * x ) - ( y * y ) has odd number of solutions , x > y and n % 12 = 11 ; Main part of Sieve of Atkin ; Mark all multiples of squares as non - prime ; Print primes using sieve [ ] ; Driver Code
< ? php function SieveOfAtkin ( $ limit ) { if ( $ limit > 2 ) echo 2 , " ▁ " ; if ( $ limit > 3 ) echo 3 , " ▁ " ; $ sieve [ $ limit ] = 0 ; for ( $ i = 0 ; $ i < $ limit ; $ i ++ ) $ sieve [ $ i ] = false ; for ( $ x = 1 ; $ x * $ x < $ limit ; $ x ++ ) { for ( $ y = 1 ; $ y * $ y < $ limit ; $ y ++ ) { $ n = ( 4 * $ x * $ x ) + ( $ y * $ y ) ; if ( $ n <= $ limit && ( $ n % 12 == 1 $ n % 12 == 5 ) ) $ sieve [ $ n ] ^= true ; $ n = ( 3 * $ x * $ x ) + ( $ y * $ y ) ; if ( $ n <= $ limit && $ n % 12 == 7 ) $ sieve [ $ n ] = true ; $ n = ( 3 * $ x * $ x ) - ( $ y * $ y ) ; if ( $ x > $ y && $ n <= $ limit && $ n % 12 == 11 ) $ sieve [ $ n ] ^= true ; } } for ( $ r = 5 ; $ r * $ r < $ limit ; $ r ++ ) { if ( $ sieve [ $ r ] ) { for ( $ i = $ r * $ r ; $ i < $ limit ; $ i += $ r * $ r ) $ sieve [ $ i ] = false ; } } for ( $ a = 5 ; $ a < $ limit ; $ a ++ ) if ( $ sieve [ $ a ] ) echo $ a , " ▁ " ; } $ limit = 20 ; SieveOfAtkin ( $ limit ) ; ? >