Count all the numbers less than 10 ^ 6 whose minimum prime factor is N | Java 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 ; Driver code ; form the sieve ; display ; display
import java . io . * ; class GFG { static int MAX = 1000000 ; static int sieve_Prime [ ] = new int [ MAX + 4 ] ; static int sieve_count [ ] = new int [ MAX + 4 ] ; static void form_sieve ( ) { sieve_Prime [ 1 ] = 1 ; for ( int i = 2 ; i <= MAX ; i ++ ) { if ( sieve_Prime [ i ] == 0 ) { for ( int j = i * 2 ; j <= MAX ; j += i ) { if ( sieve_Prime [ j ] == 0 ) { sieve_Prime [ j ] = 1 ; sieve_count [ i ] ++ ; } } } } } public static void main ( String [ ] args ) { form_sieve ( ) ; int n = 2 ; System . out . println ( " Count ▁ = ▁ " + ( sieve_count [ n ] + 1 ) ) ; n = 3 ; System . out . println ( " Count ▁ = ▁ " + ( sieve_count [ n ] + 1 ) ) ; } }