Calculating SPF ( Smallest Prime Factor ) for every number till MAXN . Time Complexity : O ( nloglogn )
def sieve ( ) : NEW_LINE INDENT spf [ 1 ] = 1 NEW_LINE for i in range ( 2 , MAXN ) : NEW_LINE DEDENT