Space optimization using bit manipulations | Python3 code to for marking multiples ; index >> 5 corresponds to dividing index by 32 index & 31 corresponds to modulo operation of index by 32 Function to check value of bit position whether it is zero or one ; Sets value of bit for corresponding index ; Driver code ; Size that will be used is actual_size / 32 ceil is used to initialize the array with positive number ; Array is dynamically initialized as we are calculating size at run time ; Iterate through every index from a to b and call setbit ( ) if it is a multiple of 2 or 5
import math NEW_LINE def checkbit ( array , index ) : NEW_LINE INDENT return array [ index >> 5 ] & ( 1 << ( index & 31 ) ) NEW_LINE DEDENT def setbit ( array , index ) : NEW_LINE INDENT array [ index >> 5 ] |= ( 1 << ( index & 31 ) ) NEW_LINE DEDENT a = 2 NEW_LINE b = 10 NEW_LINE size = abs ( b - a ) NEW_LINE size = math . ceil ( size / 32 ) NEW_LINE array = [ 0 for i in range ( size ) ] NEW_LINE for i in range ( a , b + 1 ) : NEW_LINE INDENT if ( i % 2 == 0 or i % 5 == 0 ) : NEW_LINE INDENT setbit ( array , i - a ) NEW_LINE DEDENT DEDENT print ( " MULTIPLES ▁ of ▁ 2 ▁ and ▁ 5 : " ) NEW_LINE for i in range ( a , b + 1 ) : NEW_LINE INDENT if ( checkbit ( array , i - a ) ) : NEW_LINE INDENT print ( i , end = " ▁ " ) NEW_LINE DEDENT DEDENT