Count of distinct Primonacci Numbers in a given range [ L , R ] | Java Program to implement 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
import java . util . * ; class GFG { static ArrayList < Integer > primes ; static int M = 100005 ; static void sieve ( ) { primes = new ArrayList < > ( ) ; boolean mark [ ] = new boolean [ M ] ; for ( int i = 2 ; i < M ; i ++ ) mark [ i ] = true ; for ( int i = 2 ; i * i < M ; i ++ ) { if ( mark [ i ] ) { for ( int j = i * i ; j < M ; j += i ) mark [ j ] = false ; } } for ( int i = 2 ; i < M ; i ++ ) if ( mark [ i ] ) primes . add ( i ) ; } static void countPrimonacci ( int l , int r ) { ArrayList < Integer > dp = new ArrayList < > ( ) ; dp . add ( 1 ) ; dp . add ( 1 ) ; int i = 2 ; HashSet < Integer > s = new HashSet < > ( ) ; while ( true ) { int x = 0 ; for ( int j = 0 ; j < primes . size ( ) ; j ++ ) { int p = primes . get ( j ) ; if ( p >= i ) break ; x += dp . get ( i - p ) ; } if ( x >= l && x <= r ) s . add ( x ) ; if ( x > r ) break ; dp . add ( x ) ; i ++ ; } System . out . println ( s . size ( ) ) ; } public static void main ( String [ ] args ) { sieve ( ) ; int L = 1 , R = 10 ; countPrimonacci ( L , R ) ; } }