Count all the numbers less than 10 ^ 6 whose minimum prime factor is N | Python3 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
MAX = 1000000 NEW_LINE sieve_Prime = [ 0 for i in range ( MAX + 4 ) ] NEW_LINE sieve_count = [ 0 for i in range ( MAX + 4 ) ] NEW_LINE def form_sieve ( ) : NEW_LINE INDENT sieve_Prime [ 1 ] = 1 NEW_LINE for i in range ( 2 , MAX + 1 ) : NEW_LINE INDENT if sieve_Prime [ i ] == 0 : NEW_LINE INDENT for j in range ( i * 2 , MAX + 1 , i ) : NEW_LINE INDENT if sieve_Prime [ j ] == 0 : NEW_LINE INDENT sieve_Prime [ j ] = 1 NEW_LINE sieve_count [ i ] += 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT form_sieve ( ) NEW_LINE n = 2 NEW_LINE print ( " Count ▁ = " , sieve_count [ n ] + 1 ) NEW_LINE n = 3 NEW_LINE print ( " Count ▁ = " , sieve_count [ n ] + 1 ) NEW_LINE