Count of distinct Primonacci Numbers in a given range [ L , R ] | Python3 implementation of the above approach ; Stores list of all primes ; Function to find all primes ; To mark the prime ones ; Initially all indices as prime ; If i is prime ; Set all multiples of i as non - prime ; Adding all primes to a list ; Function to return the count of Primonacci Numbers in the range [ l , r ] ; dp [ i ] contains ith Primonacci Number ; Stores the Primonacci Numbers ; Iterate over all smaller primes ; If Primonacci number lies within the range [ L , R ] ; Count of Primonacci Numbers ; Driver Code
M = 100005 NEW_LINE primes = [ ] NEW_LINE def sieve ( ) : NEW_LINE INDENT mark = [ False ] * M NEW_LINE for i in range ( 2 , M ) : NEW_LINE INDENT mark [ i ] = True NEW_LINE DEDENT i = 2 NEW_LINE while i * i < M : NEW_LINE INDENT if ( mark [ i ] ) : NEW_LINE INDENT j = i * i NEW_LINE while j < M : NEW_LINE INDENT mark [ j ] = False NEW_LINE j += i NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT for i in range ( 2 , M ) : NEW_LINE INDENT if ( mark [ i ] ) : NEW_LINE INDENT primes . append ( i ) NEW_LINE DEDENT DEDENT DEDENT def countPrimonacci ( l , r ) : NEW_LINE INDENT dp = [ ] NEW_LINE dp . append ( 1 ) NEW_LINE dp . append ( 1 ) NEW_LINE i = 2 NEW_LINE s = set ( ) NEW_LINE while ( True ) : NEW_LINE INDENT x = 0 NEW_LINE for j in range ( len ( primes ) ) : NEW_LINE INDENT p = primes [ j ] NEW_LINE if ( p >= i ) : NEW_LINE INDENT break NEW_LINE DEDENT x += dp [ i - p ] NEW_LINE DEDENT if ( x >= l and x <= r ) : NEW_LINE INDENT s . add ( x ) NEW_LINE DEDENT if ( x > r ) : NEW_LINE INDENT break NEW_LINE DEDENT dp . append ( x ) NEW_LINE i += 1 NEW_LINE DEDENT print ( len ( s ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT sieve ( ) NEW_LINE L , R = 1 , 10 NEW_LINE countPrimonacci ( L , R ) NEW_LINE DEDENT