Count numbers from a given range having exactly 5 distinct factors | C ++ Program to implement the above approach ; Stores all prime numbers up to 2 * 10 ^ 5 ; Function to generate all prime numbers up to 2 * 10 ^ 5 using Sieve of Eratosthenes ; Mark 0 and 1 as non - prime ; If i is prime ; Mark all its factors as non - prime ; If current number is prime ; Store the prime ; Function to count numbers in the range [ L , R ] having exactly 5 factors ; Stores the required count ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 2e5 ; vector < long long > prime ; void Sieve ( ) { prime . clear ( ) ; vector < bool > p ( N + 1 , true ) ; p [ 0 ] = p [ 1 ] = false ; for ( int i = 2 ; i * i <= N ; i ++ ) { if ( p [ i ] == true ) { for ( int j = i * i ; j <= N ; j += i ) { p [ j ] = false ; } } } for ( int i = 1 ; i < N ; i ++ ) { if ( p [ i ] ) { prime . push_back ( 1LL * pow ( i , 4 ) ) ; } } } void countNumbers ( long long int L , long long int R ) { int Count = 0 ; for ( int p : prime ) { if ( p >= L && p <= R ) { Count ++ ; } } cout << Count << endl ; } int main ( ) { long long L = 16 , R = 85000 ; Sieve ( ) ; countNumbers ( L , R ) ; return 0 ; }