Queries to find whether a number has exactly four distinct factors or not | C ++ program to check whether number has exactly four distinct factors or not ; Initialize global variable according to given condition so that it can be accessible to all function ; Function to calculate all number having four distinct distinct factors ; Create a boolean array " prime [ 0 . . n ] " and initialize all entries it as true . A value in prime [ i ] will finally be false if i is not a prime , else true . ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p ; Initialize prime [ ] array which will contains all the primes from 1 - N ; Iterate over all the prime numbers ; Mark cube root of prime numbers ; Mark product of prime numbers ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 1e6 ; bool fourDiv [ N + 1 ] ; memset ( fourDiv , false , sizeof ( fourDiv ) ) ; void fourDistinctFactors ( ) { bool primeAll [ N + 1 ] ; memset ( primeAll , true , sizeof ( primeAll ) ) ; for ( int p = 2 ; p * p <= N ; p ++ ) { if ( primeAll [ p ] == true ) { for ( int i = p * 2 ; i <= N ; i += p ) primeAll [ i ] = false ; } } vector < int > prime ; for ( int p = 2 ; p <= N ; p ++ ) if ( primeAll [ p ] ) prime . push_back ( p ) ; for ( int i = 0 ; i < prime . size ( ) ; ++ i ) { int p = prime [ i ] ; if ( 1LL * p * p * p <= N ) fourDiv [ p * p * p ] = true ; for ( int j = i + 1 ; j < prime . size ( ) ; ++ j ) { int q = prime [ j ] ; if ( 1LL * p * q > N ) break ; fourDiv [ p * q ] = true ; } } } int main ( ) { fourDistinctFactors ( ) ; int num = 10 ; if ( fourDiv [ num ] ) cout << " Yes STRNEWLINE " ; else cout << " No STRNEWLINE " ; num = 12 ; if ( fourDiv [ num ] ) cout << " Yes STRNEWLINE " ; else cout << " No STRNEWLINE " ; return 0 ; }