Use Sieve of Eratosthenes to find all primes smaller than n
$ isPrime = array_fill ( 0 , $ n + 1 , true ) ; for ( $ i = 2 ; $ i * $ i <= $ n ; $ i ++ ) { if ( $ isPrime [ $ i ] ) { for ( $ j = 2 * $ i ; $ j <= $ n ; $ j += $ i ) $ isPrime [ $ j ] = 0 ; } }