Count all the numbers less than 10 ^ 6 whose minimum prime factor is N | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1000000 NEW_LINE int sieve_Prime [ MAX + 4 ] = { 0 } , sieve_count [ MAX + 4 ] = { 0 } ; 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 ] ++ ; } } } } } int main ( ) { form_sieve ( ) ; int n = 2 ; cout << " Count ▁ = ▁ " << ( sieve_count [ n ] + 1 ) << endl ; n = 3 ; cout << " Count ▁ = ▁ " << ( sieve_count [ n ] + 1 ) << endl ; return 0 ; }