Queries to find whether a 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 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 contain all the primes from 1 - N ; Iterate over all the prime numbers ; Mark cube root of prime numbers ; Mark product of prime numbers ; Driver Code
N = 1000001 ; NEW_LINE fourDiv = [ False ] * ( N + 1 ) ; NEW_LINE def fourDistinctFactors ( ) : NEW_LINE INDENT primeAll = [ True ] * ( N + 1 ) ; NEW_LINE p = 2 ; NEW_LINE while ( p * p <= N ) : NEW_LINE INDENT if ( primeAll [ p ] == True ) : NEW_LINE INDENT i = p * 2 ; NEW_LINE while ( i <= N ) : NEW_LINE INDENT primeAll [ i ] = False ; NEW_LINE i += p ; NEW_LINE DEDENT DEDENT p += 1 ; NEW_LINE DEDENT prime = [ ] ; NEW_LINE for p in range ( 2 , N + 1 ) : NEW_LINE INDENT if ( primeAll [ p ] ) : NEW_LINE INDENT prime . append ( p ) ; NEW_LINE DEDENT DEDENT for i in range ( len ( prime ) ) : NEW_LINE INDENT p = prime [ i ] ; NEW_LINE if ( 1 * p * p * p <= N ) : NEW_LINE INDENT fourDiv [ p * p * p ] = True ; NEW_LINE DEDENT for j in range ( i + 1 , len ( prime ) ) : NEW_LINE INDENT q = prime [ j ] ; NEW_LINE if ( 1 * p * q > N ) : NEW_LINE INDENT break ; NEW_LINE DEDENT fourDiv [ p * q ] = True ; NEW_LINE DEDENT DEDENT DEDENT fourDistinctFactors ( ) ; NEW_LINE num = 10 ; NEW_LINE if ( fourDiv [ num ] ) : NEW_LINE INDENT print ( " Yes " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) ; NEW_LINE DEDENT num = 12 ; NEW_LINE if ( fourDiv [ num ] ) : NEW_LINE INDENT print ( " Yes " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) ; NEW_LINE DEDENT