Find minimum number of Log value needed to calculate Log upto N | Python3 program to find number of log values needed to calculate all the log values from 1 to N ; In this list prime [ i ] will store true if prime [ i ] is prime , else store false ; Using sieve of Eratosthenes to find all prime upto N ; Function to find number of log values needed to calculate all the log values from 1 to N ; calculate primes upto N ; Driver code
MAX = 1000005 NEW_LINE prime = [ True for i in range ( MAX ) ] NEW_LINE def sieve ( N ) : NEW_LINE INDENT prime [ 0 ] , prime [ 1 ] = False , False NEW_LINE for i in range ( 2 , N + 1 ) : NEW_LINE INDENT if ( prime [ i ] ) : NEW_LINE INDENT for j in range ( 2 , N + 1 ) : NEW_LINE INDENT if ( i * j > N ) : NEW_LINE INDENT break NEW_LINE DEDENT prime [ i * j ] = False NEW_LINE DEDENT DEDENT DEDENT DEDENT def countLogNeeded ( N ) : NEW_LINE INDENT count = 0 NEW_LINE sieve ( N ) NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT if ( prime [ i ] ) : NEW_LINE INDENT count = count + 1 NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 6 NEW_LINE print ( countLogNeeded ( N ) ) NEW_LINE DEDENT