Count of elements having Euler 's Totient value one less than itself | C ++ program for the above approach ; Seiev of Erotosthenes method to compute all primes ; If current number is marked prime then mark its multiple as non - prime ; Function to count the number of element satisfying the condition ; Compute the number of primes in count prime array ; Print the number of elements satisfying the condition ; Driver Code ; Given array ; Size of the array ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long prime [ 1000001 ] = { 0 } ; void seiveOfEratosthenes ( ) { for ( int i = 2 ; i < 1000001 ; i ++ ) { prime [ i ] = 1 ; } for ( int i = 2 ; i * i < 1000001 ; i ++ ) { if ( prime [ i ] == 1 ) { for ( int j = i * i ; j < 1000001 ; j += i ) { prime [ j ] = 0 ; } } } } void CountElements ( int arr [ ] , int n , int L , int R ) { seiveOfEratosthenes ( ) ; long long countPrime [ n + 1 ] = { 0 } ; for ( int i = 1 ; i <= n ; i ++ ) { countPrime [ i ] = countPrime [ i - 1 ] + prime [ arr [ i - 1 ] ] ; } cout << countPrime [ R ] - countPrime [ L - 1 ] << endl ; return ; } int main ( ) { int arr [ ] = { 2 , 4 , 5 , 8 } ; int N = sizeof ( arr ) / sizeof ( int ) ; int L = 1 , R = 3 ; CountElements ( arr , N , L , R ) ; return 0 ; }