Count all the numbers less than 10 ^ 6 whose minimum prime factor is N | Javascript 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
var MAX = 1000000 ; var sieve_Prime = Array . from ( { length : MAX + 4 } , ( _ , i ) => 0 ) ; var sieve_count = Array . from ( { length : MAX + 4 } , ( _ , i ) => 0 ) ; function form_sieve ( ) { 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 ( ) ; var n = 2 ; document . write ( " " + ( sieve_count [ n ] + 1 ) ) ; n = 3 ; document . write ( " " + ( sieve_count [ n ] + 1 ) ) ;