Count of distinct Primonacci Numbers in a given range [ L , R ] | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; static vector < int > primes ; int M = 100005 ; void sieve ( ) { bool mark [ M ] ; for ( int i = 0 ; i < M ; i ++ ) mark [ i ] = false ; 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 . push_back ( i ) ; } void countPrimonacci ( int l , int r ) { vector < int > dp ; dp . push_back ( 1 ) ; dp . push_back ( 1 ) ; int i = 2 ; set < int > s ; while ( true ) { int x = 0 ; for ( int j = 0 ; j < primes . size ( ) ; j ++ ) { int p = primes [ j ] ; if ( p >= i ) break ; x += dp [ i - p ] ; } if ( x >= l && x <= r ) s . insert ( x ) ; if ( x > r ) break ; dp . push_back ( x ) ; i ++ ; } cout << s . size ( ) ; } int main ( ) { sieve ( ) ; int L = 1 , R = 10 ; countPrimonacci ( L , R ) ; }