Count of distinct Primonacci Numbers in a given range [ L , R ] | 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
let primes = new Array ( ) ; let M = 100005 ; function sieve ( ) { let mark = new Array ( M ) ; for ( let i = 0 ; i < M ; i ++ ) mark [ i ] = false ; for ( let i = 2 ; i < M ; i ++ ) mark [ i ] = true ; for ( let i = 2 ; i * i < M ; i ++ ) { if ( mark [ i ] ) { for ( let j = i * i ; j < M ; j += i ) mark [ j ] = false ; } } for ( let i = 2 ; i < M ; i ++ ) if ( mark [ i ] ) primes . push ( i ) ; } function countPrimonacci ( l , r ) { let dp = new Array ( ) ; dp . push ( 1 ) ; dp . push ( 1 ) ; let i = 2 ; let s = new Set ( ) ; while ( true ) { let x = 0 ; for ( let j = 0 ; j < primes . length ; j ++ ) { let p = primes [ j ] ; if ( p >= i ) break ; x += dp [ i - p ] ; } if ( x >= l && x <= r ) s . add ( x ) ; if ( x > r ) break ; dp . push ( x ) ; i ++ ; } document . write ( s . size ) ; } sieve ( ) ; let L = 1 , R = 10 ; countPrimonacci ( L , R ) ;