Count all the numbers less than 10 ^ 6 whose minimum prime factor is N | PHP implementation of above approach ; the sieve of prime number and count of minimum prime factor ; form the prime sieve ; 1 is not a prime number ; form the sieve ; if i is prime ; if i is the least prime factor ; mark the number j as non prime ; count the numbers whose least prime factor is i ; form the sieve ; display ; display
< ? php $ MAX = 1000000 ; $ sieve_Prime = array_fill ( 0 , $ MAX + 4 , NULL ) ; $ sieve_count = array_fill ( 0 , $ MAX + 4 , NULL ) ; function form_sieve ( ) { global $ sieve_Prime , $ sieve_count , $ MAX ; $ sieve_Prime [ 1 ] = 1 ; for ( $ i = 2 ; $ i <= $ MAX ; $ i ++ ) { if ( $ sieve_Prime [ $ i ] == 0 ) { for ( $ j = $ i * 2 ; $ j <= $ MAX ; $ j += $ i ) { if ( $ sieve_Prime [ $ j ] == 0 ) { $ sieve_Prime [ $ j ] = 1 ; $ sieve_count [ $ i ] ++ ; } } } } } form_sieve ( ) ; $ n = 2 ; echo " Count = " ▁ . ▁ ( $ sieve _ count [ $ n ] ▁ + ▁ 1 ) ▁ . ▁ " " $ n = 3 ; echo " Count = " ▁ . ▁ ( $ sieve _ count [ $ n ] ▁ + ▁ 1 ) ▁ . ▁ " " ? >